モジュラー冪乗計算機

モジュラー冪乗計算機

モジュラー冪乗計算機は、\(a^b \bmod n\) を計算します。これは、底 \(a\) を指数 \(b\) で累乗し、法 \(n\) で割った余りを求める操作です。この電卓は、演算回数を \(O(b)\) 回の乗算からわずか \(O(\log b)\) 回に削減する バイナリ冪乗法（高速累乗法や繰り返し二乗法とも呼ばれます）を使用しています。これは、RSA、Diffie-Hellman、ElGamal などの実際の暗号実装で使用されているのと同じアルゴリズムです。

モジュラー冪乗の用途

バイナリ冪乗法アルゴリズムの仕組み

重要な洞察は、任意の指数をバイナリ表現（2進数）を使用して2の累乗の和に分解できることです。例えば、\(b = 13 = 1101_2 = 2^3 + 2^2 + 2^0\) なので、\(a^{13} = a^{8} \times a^{4} \times a^{1}\) となります。

アルゴリズムは、指数のバイナリ数字を左から右へと処理します：

擬似コード

function modpow(base, exp, mod):
    result = 1
    base = base mod mod
    while exp > 0:
        if exp is odd:        // ビットが 1 の場合
            result = (result × base) mod mod
        exp = exp >> 1        // 右シフト（2で割る）
        base = (base × base) mod mod
    return result

主な公式

モジュラー冪乗計算機の使い方

1. 底 (a) を入力: 累乗したい数値を入力します。正負どちらも可能です。例えば、7^256 mod 13 を計算する場合は 7 を入力します。
2. 指数 (b) を入力: 非負の整数である必要があります。これは累乗のパワーを表します。暗号用途では非常に大きな値になることがありますが、この電卓は 10^18 までサポートしています。
3. 法 (n) を入力: 正の整数である必要があります。これは割り算をして余りを求めるための数値です。RSA では通常、2つの大きな素数の積になります。
4. 計算をクリック: 電卓はバイナリ冪乗法を使用して a^b mod n を計算し、即座に結果を表示します。
5. アニメーションを見る: 「再生」を押すと、バイナリ冪乗法アルゴリズムがステップごとに実行される様子を確認できます。指数の各ビットが順番に処理され、アルゴリズムが「二乗」のみを行うか、「二乗して乗算」を行うかが示されます。
6. 追跡データを確認: ステップごとの表にはすべての中間計算が表示され、効率の比較では、バイナリ冪乗法が素朴な連続乗算よりもどれだけ速いかが示されます。

なぜバイナリ冪乗法は速いのか

\(2^{1000} \bmod 13\) の計算を考えてみましょう。素朴な方法では 999 回の乗算が必要です。バイナリ冪乗法では 1000 をバイナリ（1111101000）に変換しますが、これは 10 ビットです。必要なのは最大 9 回の二乗と、ビットが「1」の場所での数回の乗算だけで、合計約 15 回の演算で済みます。これは 約 98.5% の演算削減 になります。数百桁の指数を持つ暗号規模の計算では、その差は天文学的です。バイナリ法では数千回の演算で済みますが、素朴な方法では宇宙にある原子の数よりも多くの演算が必要になってしまいます。

FAQ