模冪

模冪（英語：modular exponentiation）是一種對模進行的冪運算，在電腦科學，尤其是公開金鑰加密方面有一定用途。

模冪運算是指求整數${\displaystyle b}$的${\displaystyle e}$次方${\displaystyle b^{e}}$被正整數${\displaystyle m}$所除得到的餘數${\displaystyle c}$的過程，可用數學符號表示為${\displaystyle c=b^{e}{\bmod {m}}}$。由${\displaystyle c}$的定義可得${\displaystyle 0\leq c<m}$。

例如，給定${\displaystyle b=5}$，${\displaystyle e=3}$和${\displaystyle m=13}$，${\displaystyle 5^{3}=125}$被13除得的餘數${\displaystyle c=8}$。

指數${\displaystyle e}$為負數時可使用擴充歐幾里得演算法找到${\displaystyle b}$模除${\displaystyle m}$的模反元素${\displaystyle d}$來執行模冪運算，即：

${\displaystyle c=b^{e}{\bmod {m}}=d^{-e}{\bmod {m}}}$，其中 ${\displaystyle e<0}$且${\displaystyle b\cdot d\equiv 1{\pmod {m}}}$。

即使在整數很大的情況下，上述模冪運算其實也是易於執行的。然而，計算模的離散對數（即在已知${\displaystyle b}$，${\displaystyle c}$和${\displaystyle m}$時求出指數${\displaystyle e}$）則較為困難。這種類似單向函數的表現使模冪運算可用於加密演算法。

直接演算法

計算模冪的最直接方法是直接算出${\displaystyle b^{e}}$，再把結果模除${\displaystyle m}$。假設已知${\displaystyle b=4}$，${\displaystyle e=13}$，以及${\displaystyle m=497}$，要求${\displaystyle c}$：

${\displaystyle c\equiv 4^{13}{\pmod {497}}}$

可用計數機算得4¹³結果為67,108,864，模除497，可得c等於445。

注意到${\displaystyle b}$只有一位，${\displaystyle e}$也只有兩位，但${\displaystyle b^{e}}$的值卻有8位元。

強加密時${\displaystyle b}$通常至少有1024位元^[1]。考慮${\displaystyle b=5\times 10^{76}}$和${\displaystyle e=17}$的情況，${\displaystyle b}$的長度為77位，${\displaystyle e}$的長度為2位，但是${\displaystyle b^{e}}$的值以十進制表示卻已經有1304位元。現代電腦雖然可以進行這種計算，但計算速度卻大大降低。

用這種演算法求模冪所需的時間取決於操作環境和處理器，時間複雜度為${\displaystyle \mathrm {O} (e)}$。

空間最佳化

這種方法比第一種所需要的步驟更多，但所需主記憶體空間和時間均大為減少，其原理為： 給定兩個整數${\displaystyle a}$和${\displaystyle b}$，以下兩個等式是等價的^{[錨點失效]}：

${\displaystyle c{\bmod {m}}=(a\cdot b){\bmod {m}}}$

${\displaystyle c{\bmod {m}}=[(a{\bmod {m}})\cdot (b{\bmod {m}})]{\bmod {m}}}$

演算法如下：

1. 令${\displaystyle c=1}$，${\displaystyle e'=0}$。
2. ${\displaystyle e'}$自增1。
3. 令${\displaystyle c=(b\cdot c){\bmod {m}}}$.
4. 若${\displaystyle e'<e}$，則返回第二步；否則，${\displaystyle c}$即為${\displaystyle c\equiv b^{e}{\pmod {m}}}$。

再以${\displaystyle b=4}$，${\displaystyle e=13}$，${\displaystyle m=497}$為例說明，演算法第三步需要執行13次：

• ${\displaystyle e'=1\cdot c=(1\cdot 4){\bmod {4}}97=4{\bmod {4}}97=4}$
• ${\displaystyle e'=2\cdot c=(4\cdot 4){\bmod {4}}97=16{\bmod {4}}97=16}$
• ${\displaystyle e'=3\cdot c=(16\cdot 4){\bmod {4}}97=64{\bmod {4}}97=64}$
• ${\displaystyle e'=4\cdot c=(64\cdot 4){\bmod {4}}97=256{\bmod {4}}97=256}$
• ${\displaystyle e'=5\cdot c=(256\cdot 4){\bmod {4}}97=1024{\bmod {4}}97=30}$
• ${\displaystyle e'=6\cdot c=(30\cdot 4){\bmod {4}}97=120{\bmod {4}}97=120}$
• ${\displaystyle e'=7\cdot c=(120\cdot 4){\bmod {4}}97=480{\bmod {4}}97=480}$
• ${\displaystyle e'=8\cdot c=(480\cdot 4){\bmod {4}}97=1920{\bmod {4}}97=429}$
• ${\displaystyle e'=9\cdot c=(429\cdot 4){\bmod {4}}97=1716{\bmod {4}}97=225}$
• ${\displaystyle e'=10\cdot c=(225\cdot 4){\bmod {4}}97=900{\bmod {4}}97=403}$
• ${\displaystyle e'=11\cdot c=(403\cdot 4){\bmod {4}}97=1612{\bmod {4}}97=121}$
• ${\displaystyle e'=12\cdot c=(121\cdot 4){\bmod {4}}97=484{\bmod {4}}97=484}$
• ${\displaystyle e'=13\cdot c=(484\cdot 4){\bmod {4}}97=1936{\bmod {4}}97=445}$

因此最終結果${\displaystyle c}$為445，與第一種方法所求結果相等。

與第一種方法相同，這種演算法需要${\displaystyle \mathrm {O} (e)}$的時間才能完成。但是，由於在計算過程中處理的數字比第一種演算法小得多，因此計算時間至少減少了${\displaystyle \mathrm {O} (e)}$倍。

演算法偽代碼如下：

function modular_pow(b, e, m)
    if m = 1
        then return 0
    c := 1
    for e' = 0 to e-1
        c := (c * b) mod m
    return c

從右到左二位演算法

第三種方法結合了第二種演算法和平方求冪原理，使所需步驟大大減少，同時也與第二種方法一樣減少了主記憶體佔用量。

首先把${\displaystyle e}$表示成二進制，即：

${\displaystyle e=\sum _{i=0}^{n-1}a_{i}2^{i}}$

此時${\displaystyle e}$的長度為${\displaystyle n}$位。對任意${\displaystyle i}$（${\displaystyle 0\leq i<n}$），${\displaystyle a_{i}}$可取0或1任一值。由定義有${\displaystyle a_{n-1}=1}$。

${\displaystyle b^{e}}$的值可寫作：

${\displaystyle b^{e}=b^{\left(\sum _{i=0}^{n-1}a_{i}2^{i}\right)}=\prod _{i=0}^{n-1}\left(b^{2^{i}}\right)^{a_{i}}}$

因此答案${\displaystyle c}$即為：

${\displaystyle c\equiv \prod _{i=0}^{n-1}\left(b^{2^{i}}\right)^{a_{i}}\ ({\mbox{mod}}\ m)}$

偽代碼

下述偽代碼基於布魯斯·施奈爾所著《應用密碼學》^[2]。其中base，exponent和modulus分別對應上式中的${\displaystyle b}$，${\displaystyle e}$和${\displaystyle m}$。

function modular_pow(base, exponent, modulus)
    if modulus = 1 then return 0
    Assert :: (modulus - 1) * (modulus - 1) does not overflow base
    result := 1
    base := base mod modulus
    while exponent > 0
        if (exponent mod 2 == 1):
           result := (result * base) mod modulus
        exponent := exponent >> 1
        base := (base * base) mod modulus
    return result

注意到在首次進入迴圈時，變數base等於${\displaystyle b}$。在第三行代碼中重複執行平方運算，會確保在每次迴圈結束時，變數base等於${\displaystyle b^{2^{i}}{\bmod {m}}}$，其中${\displaystyle i}$是迴圈執行次數。

本例中，底數${\displaystyle b}$的指數為${\displaystyle e=13}$。 指數用二進制表示為1101，有4位元，故迴圈執行4次。 4位元數字從右到左依次為1，0，1，1。

首先，初始化結果${\displaystyle R}$為1，並將b的值儲存在變數${\displaystyle x}$中：

${\displaystyle R\leftarrow 1\,(=b^{0}){\text{且 }}x\leftarrow b}$.

第1步 第1位為1，故令${\displaystyle R\leftarrow R\cdot x{\text{ }}(=b^{1})}$；

令${\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{2})}$。

第2步 第2位為0，故不給R賦值；

令${\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{4})}$。

第3步 第3位為1，故令${\displaystyle R\leftarrow R\cdot x{\text{ }}(=b^{5})}$；

令${\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{8})}$。

第4步 第4位元為1，故令${\displaystyle R\leftarrow R\cdot x{\text{ }}(=b^{13})}$；

這是最後一步，所以不需要對x求平方。

綜上，${\displaystyle R}$為${\displaystyle b^{13}}$。

以下計算${\displaystyle b=4}$的${\displaystyle e=13}$次方對497求模的結果。

初始化：

${\displaystyle R\leftarrow 1\,(=b^{0})}$且${\displaystyle x\leftarrow b=4}$。

第1步 第1位為1，故令${\displaystyle R\leftarrow R\cdot 4{\pmod {497}}\equiv 4{\pmod {497}}}$；

令${\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{2})\equiv 4^{2}\equiv 16{\pmod {497}}}$。

第2步 第2位為0，故不給R賦值；

令${\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{4})\equiv 16^{2}{\pmod {497}}\equiv 256{\pmod {497}}}$。

第3步 第3位為1，故令${\displaystyle R\leftarrow R\cdot x{\text{ }}(=b^{5})\equiv 4\cdot 256{\pmod {497}}\equiv 30{\pmod {497}}}$；

令${\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{8})\equiv 256^{2}{\pmod {497}}\equiv 429{\pmod {497}}}$。

第4步 第4位元為1，故令${\displaystyle R\leftarrow R\cdot x{\text{ }}(=b^{13})\equiv 30\cdot 429{\pmod {497}}\equiv 445{\pmod {497}}}$；

綜上，${\displaystyle R}$為${\displaystyle 4^{13}{\pmod {497}}\equiv 445{\pmod {497}}}$，與先前演算法中所得結果相同。

該演算法時間複雜度為O(log exponent)。指數exponent值較大時，這種演算法與前兩種O(exponent)演算法相比具有明顯的速度優勢。例如，如果指數為2²⁰ = 1048576，此演算法只需執行20步，而非1,048,576步。

Lua實現

function modPow(b,e,m)
        if m == 1 then
                return 0
        else
                local r = 1
                b = b % m
                while e > 0 do
                        if e % 2 == 1 then
                                r = (r*b) % m
                        end
                        e = e >> 1     --Lua 5.2或更早版本使用e = math.floor(e / 2)
                        b = (b^2) % m
                end
                return r
        end
end

軟件實現

鑑於模冪運算是電腦科學中的重要操作，並且已有高效演算法，所以許多程式語言和高精度整數庫都有執行模冪運算的函數：

• Python內建的pow()（求冪）函數[1] （頁面存檔備份，存於互聯網檔案館）
• .NET框架的BigInteger類的ModPow()方法
• Java的java.math.BigInteger類的modPow()方法
• Perl的Math::BigInt模組的bmodpow()方法[2] （頁面存檔備份，存於互聯網檔案館）
• Raku內建的expmod常式
• Go的big.Int類的Exp()（求冪）方法[3] （頁面存檔備份，存於互聯網檔案館）
• PHP的BC Math庫的bcpowmod()函數[4] （頁面存檔備份，存於互聯網檔案館）
• GNU多重精度運算庫（GMP）的mpz_powm()函數[5] （頁面存檔備份，存於互聯網檔案館）
• FileMaker Pro的@PowerMod()函數（以1024位元RSA加密為例）
• Ruby的openssl包的OpenSSL::BN#mod_exp方法[6] （頁面存檔備份，存於互聯網檔案館）
• HP Prime計數機的CAS.powmod()函數[7]^{[失效連結]}

另見

• 蒙哥馬利演算法，用於計算模很大時的餘數。

參考資料

1. Weak Diffie-Hellman and the Logjam Attack. weakdh.org. [2019-05-03]. （原始內容存檔於2021-03-29）.
2. Schneier 1996, p. 244.

外部連結

• Schneier, Bruce. Applied Cryptography: Protocols, Algorithms, and Source Code in C, Second Edition 2nd. Wiley. 1996. ISBN 978-0-471-11709-4.
• Paul Garrett, Fast Modular Exponentiation Java Applet （頁面存檔備份，存於互聯網檔案館）
• Gordon, Daniel M. A Survey of Fast Exponentiation Methods (PDF). Journal of Algorithms (Elsevier BV). 1998, 27 (1): 129–146 [2019-11-30]. ISSN 0196-6774. doi:10.1006/jagm.1997.0913. （原始內容存檔 (PDF)於2019-08-27）.