べき乗剰余計算機とは？
べき乗剰余計算機は \((\text{base}^{\text{exponent}}) \bmod m\)、つまり「底をべき乗した値を法（モジュラス）で割った余り」を求めるツールです。この演算は「モジュラ指数演算（べき乗剰余）」と呼ばれ、整数論や暗号技術のいたるところで活躍します。RSA暗号、ディフィー・ヘルマン鍵交換、素数判定、ハッシュ関数などの基盤となる計算です。底を実際にべき乗してから余りを取る方法では、指数が大きいと天文学的な桁数になってしまい計算不能になるため、ここでは高速なアルゴリズムを使います。
使い方
3つの整数を入力します。底（base）、指数（exponent、0以上）、そして法（modulus）m（1より大きい正の整数）です。「計算」を押すと、結果が 0 から m−1 の範囲で返されます。底が負の数の場合も、自動的に正しい非負の剰余に変換されます。
計算の仕組み
本計算機は、巨大な \(\text{base}^{\text{exponent}}\) をそのまま作ることはせず、二乗・乗算法（バイナリ法、繰り返し二乗法）を用います。まず指数を2進数として読み取り、結果の初期値を1とします。そこから底を法 m のもとで繰り返し二乗していき、その時点の指数の2進桁が1のときだけ、二乗した値を結果に掛け合わせ、再び m で割った余りを取ります。途中に現れる数は常に \(m^2\) より小さく保たれるため、指数が数百桁あっても高速に計算できます。
計算例
\(7^{256} \bmod 13\) を求めてみましょう。13を法とした7の位数は12の約数で、\(7^{12} \equiv 1\) が成り立ちます。\(256 = 12 \times 21 + 4\) なので、$$7^{256} \equiv 7^4 = 2401 \equiv 9 \pmod{13}$$となります。よって答えは 9。217桁にもなる \(7^{256}\) を一度も作ることなく、瞬時に求められます。
よくある質問
法（m）が1のときは？ どんな整数も1を法とすると0と合同なので、結果は0になります。
指数を0にできますか？ はい。どんな底でも0乗は1なので、結果は \(1 \bmod m\)（m > 1 のときは1）になります。
そのままべき乗を計算してはいけないの？ 指数が大きいと途中の数が膨大な桁数になり、オーバーフローしてしまいます。各ステップで剰余を取ることで値を小さく保ち、効率よく計算できるのです。
