模冪運算計算機

模冪運算計算機

模冪運算計算機計算 \(a^b \bmod n\) — 將底數 \(a\) 提高到指數 \(b\) 的冪次，並取除以模數 \(n\) 後的餘數。它使用二進位冪運算法（也稱為快速冪或平方求冪），將運算從 \(O(b)\) 次乘法減少到僅 \(O(\log b)\) 次。這與 RSA、Diffie-Hellman 和 ElGamal 等實際密碼學實作中所使用的演算法相同。

模冪運算的應用

二進位冪運算法的工作原理

核心概念是我們可以利用二進位表示法，將任何指數分解為 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 以計算 7^256 mod 13。
2. 輸入指數 (b)： 這必須是非負整數。它代表冪次。對於密碼學應用，這可能非常大（本計算機支援高達 10^18）。
3. 輸入模數 (n)： 這必須是正整數。這是用來除以並獲取餘數的數字。在 RSA 中，這通常是兩個大質數的乘積。
4. 點擊計算： 計算機會使用二進位冪運算計算 a^b mod n 並立即顯示結果。
5. 觀看動畫： 按下「播放」觀看二進位冪運算演算法的逐步執行。指數的每個位元會依序處理，顯示演算法是進行平方，還是平方與相乘。
6. 查看追蹤： 逐步表格顯示了每個中間計算過程，效率對比顯示了二進位冪運算比樸素重複乘法快多少。

為什麼二進位冪運算很快

考慮計算 \(2^{1000} \bmod 13\)。樸素方法需要 999 次乘法。二進位冪運算將 1000 轉換為二進位 (1111101000)，共有 10 個位元。它只需要最多 9 次平方加上每個「1」位元的幾次乘法——總共約 15 次操作。這大約減少了 98.5% 的操作次數。對於具有數百位數字的密碼學規模指數，差異是天文數字：二進位方法需要數千次操作，而樸素方法需要的操作次數將超過宇宙中的原子數量。

常見問題 (FAQ)