累乗剰余を効率的に計算する
square-and-multiply(繰り返し二乗法)を使って base^exponent mod modulus を効率的に計算します。暗号技術の基礎となります。
- 1
累乗剰余は、巨大な base^exp を先に計算することなく、base^exp mod m を求めます。square-and-multiply(繰り返し二乗法)は指数の各ビットを処理します。各ビットで結果を二乗し、ビットが 1 なら base を掛け、各ステップで mod を取ります。これにより O(exp) ではなく O(log exp) で済みます。指数が 2048 ビット以上になる暗号技術では決定的に重要です。
- 2 剰余べき乗計算ツール →
base^exp mod m を直接計算します。底、指数、法を入力してください。ツールは効率的なアルゴリズムを使うため、2048 ビットの指数でも瞬時に完了します。RSA や Diffie-Hellman などの暗号操作の基盤です。
- 3 高精度計算ツール →
小さい数で結果を検証しましょう。例:3^5 mod 7 = 243 mod 7 = 5。累乗剰余ツールも同じ結果を返すはずです。この健全性チェックで、アルゴリズムが正しく動作していることを確認できます。
よくある質問
- 暗号技術で素朴な累乗が実用的でないのはなぜ?
- RSA は 2048 ビット以上の指数を使います。2^2048 は 617 桁の数であり、直接計算には地球上に存在するメモリを超える容量が必要になります。累乗剰余は各ステップで mod を取るため中間結果を常に小さく保ち(m 未満)、実行可能にします。
- square-and-multiply アルゴリズムとは?
- 指数をビットごとに処理します。result = 1 から始め、各ビット(最上位ビットから最下位ビットへ)について:result = result^2 mod m(二乗)、ビットが 1 なら result = result × base mod m(乗算)。各ビットを最大 2 回の乗算で処理でき、合計で O(log exp) です。