べき乗剰余とは？
べき乗剰余（モジュラー指数）とは、\(a^{b} \bmod m\) ——つまりべき乗 \(a^{b}\) を法 \(m\) で割ったときの余りを求める計算です。これは整数論や暗号理論でもっとも重要な演算のひとつで、RSA や Diffie–Hellman 鍵共有、デジタル署名といったアルゴリズムを支えています。たとえ \(a^{b}\) が天文学的に巨大な値になっても、\(m\) で割った剰余は小さなまま計算できるのが大きな特徴です。
このツールの使い方
3つの整数を入力します。底 \(a\)、0以上の指数 \(b\)、そして法 \(m\)（正の整数）です。計算ボタンを押すと、0 から \(m-1\) の範囲に収まる余りが1つ得られます。底が負の数でも問題ありません。べき乗を行う前に、まず正しい剰余の範囲へ変換（正規化）されます。
計算の仕組み
\(b\) が大きい場合、\(a^{b}\) を直接計算するのは現実的ではありません。そこでこのツールは 繰り返し二乗法（高速べき乗法、バイナリ法とも呼ばれます）を使います。指数を2進数として読み取り、結果 \(r = 1\)、底を \(\bmod m\) で簡約した状態からスタートします。指数の各ビットについて底を2乗（\(\bmod m\)）し、そのビットが 1 のときだけ結果に底を掛け合わせ（\(\bmod m\)）ます。この方法なら、\(b\) 回の掛け算ではなく、おおよそ \(\log_2(b)\) 回の掛け算で済みます。
計算例
\(4^{13} \bmod 497\) を求めてみましょう。指数 13 を2進数で表すと 1101 です。繰り返し二乗法でたどると、\(4^1 = 4\)、\(4^2 = 16\)、\(4^4 = 256\)、\(4^8 = 256^2 = 65536 \equiv 30 \pmod{497}\) となります。\(13 = 8 + 4 + 1\) なので、対応するべき乗を掛け合わせます。$$30 \times 256 \times 4 = 30720 \equiv 445 \pmod{497}$$ したがって \(4^{13} \bmod 497 = \mathbf{445}\) です。
よくある質問
指数が 0 のときは？ どんな数でも 0 乗は 1 なので、結果は \(1 \bmod m\) になります（\(m = 1\) のときは 0 です）。
底が負の数でもよいですか？ はい。負の底はまず \(\bmod m\) での同値な正の剰余に変換されるため、答えは常に 0 から \(m-1\) の間に収まります。
\(a^{b}\) を計算してから mod をとってはいけないの？ 暗号で扱うような大きさになると、\(a^{b}\) は何百万桁にもなってしまいます。各ステップごとに \(\bmod m\) で簡約することで、数値を小さく保ち、計算を高速に進められるのです。
