模幂

模幂（英语：modular exponentiation）是一种对模进行的幂运算，在计算机科学，尤其是公开密钥加密方面有一定用途。

模幂运算是指求整数<math>b</math>的<math>e</math>次方<math>b^e</math>被正整数<math>m</math>所除得到的余数<math>c</math>的过程，可用数学符号表示为<math>c=b^e \bmod m</math>。由<math>c</math>的定义可得<math>0\leq c <m</math>。

例如，给定<math>b=5</math>，<math>e=3</math>和<math>m=13</math>，<math>5^3=125</math>被13除得的余数<math>c=8</math>。

指数<math>e</math>为负数时可使用扩展欧几里得算法找到<math>b</math>模除<math>m</math>的模逆元<math>d</math>来执行模幂运算，即：

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

即使在整数很大的情况下，上述模幂运算其实也是易于执行的。然而，计算模的离散对数（即在已知<math>b</math>，<math>c</math>和<math>m</math>时求出指数<math>e</math>）则较为困难。这种类似单向函数的表现使模幂运算可用于加密算法。

直接算法[编辑]

计算模幂的最直接方法是直接算出<math>b^e</math>，再把结果模除<math>m</math>。假设已知<math>b=4</math>，<math>e=13</math>，以及<math>m=497</math>，要求<math>c</math>：

<math>c\equiv 4^{13}\pmod{497}</math>

可用计算器算得4¹³结果为67,108,864，模除497，可得 $c$ 等于445。

注意到<math>b</math>只有一位，<math>e</math>也只有两位，但<math>b^e</math>的值却有8位。

强加密时<math>b</math>通常至少有1024位^[1]。考虑<math>b=5\times 10^{76}</math>和<math>e=17</math>的情况，<math>b</math>的长度为77位，<math>e</math>的长度为2位，但是<math>b^e</math>的值以十进制表示却已经有1304位。现代计算机虽然可以进行这种计算，但计算速度却大大降低。

用这种算法求模幂所需的时间取决于操作环境和处理器，时间复杂度为<math>\mathrm{O}(e)</math>。

空间优化[编辑]

这种方法比第一种所需要的步骤更多，但所需内存空间和时间均大为减少，其原理为：给定两个整数<math>a</math>和<math>b</math>，以下两个等式是等价的：

算法如下：

令<math>c=1</math>，<math>e'=0</math>。
<math>e'</math>自增1。
令<math>c=(b\cdot c) \bmod m</math>.
若<math>e'<e</math>，则返回第二步；否则，<math>c</math>即为<math>c\equiv b^e \pmod{m}</math>。

再以<math>b=4</math>，<math>e=13</math>，<math>m=497</math>为例说明，算法第三步需要执行13次：

<math>e' = 1\cdot c=(1\cdot 4) \bmod 497=4 \bmod 497=4</math>
<math>e' = 2\cdot c=(4\cdot 4) \bmod 497=16 \bmod 497=16</math>
<math>e' = 3\cdot c=(16\cdot 4) \bmod 497=64 \bmod 497=64</math>
<math>e' = 4\cdot c=(64\cdot 4) \bmod 497=256 \bmod 497=256</math>
<math>e' = 5\cdot c=(256\cdot 4) \bmod 497=1024 \bmod 497=30</math>
<math>e' = 6\cdot c=(30\cdot 4) \bmod 497=120 \bmod 497=120</math>
<math>e' = 7\cdot c=(120\cdot 4) \bmod 497=480 \bmod 497=480</math>
<math>e' = 8\cdot c=(480\cdot 4) \bmod 497=1920 \bmod 497=429</math>
<math>e' = 9\cdot c=(429\cdot 4) \bmod 497=1716 \bmod 497=225</math>
<math>e' = 10\cdot c=(225\cdot 4) \bmod 497=900 \bmod 497=403</math>
<math>e' = 11\cdot c=(403\cdot 4) \bmod 497=1612 \bmod 497=121</math>
<math>e' = 12\cdot c=(121\cdot 4) \bmod 497=484 \bmod 497=484</math>
<math>e' = 13\cdot c=(484\cdot 4) \bmod 497=1936 \bmod 497=445</math>

因此最终结果<math>c</math>为445，与第一种方法所求结果相等。

与第一种方法相同，这种算法需要<math>\mathrm{O}(e)</math>的时间才能完成。但是，由于在计算过程中处理的数字比第一种算法小得多，因此计算时间至少减少了<math>\mathrm{O}(e)</math>倍。

算法伪代码如下：

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

从右到左二位算法[编辑]

第三种方法结合了第二种算法和平方求幂原理，使所需步骤大大减少，同时也与第二种方法一样减少了内存占用量。

首先把<math>e</math>表示成二进制，即：

此时<math>e</math>的长度为<math>n</math>位。对任意<math>i</math>（<math>0\leq i < n</math>），<math>a_i</math>可取0或1任一值。由定义有<math>a_{n-1}=1</math>。

<math>b^e</math>的值可写作：

<math>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}</math>

因此答案<math>c</math>即为：

<math>c \equiv \prod_{i=0}^{n-1} \left( b^{2^i} \right) ^ {a_i}\ (\mbox{mod}\ m)</math>

伪代码[编辑]

下述伪代码基于布鲁斯·施奈尔所著《应用密码学》^[2]。其中base，exponent和modulus分别对应上式中的<math>b</math>，<math>e</math>和<math>m</math>。

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等于<math>b</math>。在第三行代码中重复执行平方运算，会确保在每次循环结束时，变量base等于<math>b^{2^i} \bmod m</math>，其中<math>i</math>是循环执行次数。

本例中，底数<math>b</math>的指数为<math>e = 13</math>。指数用二进制表示为1101，有4位，故循环执行4次。 4位数字从右到左依次为1，0，1，1。

首先，初始化结果<math>R</math>为1，并将 $b$ 的值保存在变量<math>x</math>中：

<math> R \leftarrow 1 \, ( = b^0) \text{且 } x \leftarrow b </math>.

第1步第1位为1，故令<math> R \leftarrow R \cdot x \text{ }(= b^1) </math>；

令<math> x \leftarrow x^2 \text{ }(= b^2) </math>。

第2步第2位为0，故不给

R

赋值；

令<math> x \leftarrow x^2 \text{ }(= b^4) </math>。

第3步第3位为1，故令<math> R \leftarrow R \cdot x \text{ }(= b^5) </math>；

令<math> x \leftarrow x^2 \text{ }(= b^8) </math>。

第4步第4位为1，故令<math> R \leftarrow R \cdot x \text{ }(= b^{13}) </math>；

这是最后一步，所以不需要对

x

求平方。

综上，<math>R</math>为<math>b^{13}</math>。

以下计算<math>b = 4</math>的<math>e = 13</math>次方对497求模的结果。

初始化：

<math> R \leftarrow 1 \, ( = b^0) </math>且<math> x \leftarrow b = 4 </math>。

第1步第1位为1，故令<math>R \leftarrow R \cdot 4 \pmod {497} \equiv 4 \pmod{497} </math>；

令<math> x \leftarrow x^2 \text{ }(= b^2) \equiv 4^2 \equiv 16 \pmod{497} </math>。

第2步第2位为0，故不给

R

赋值；

令<math> x \leftarrow x^2 \text{ }(= b^4) \equiv 16^2 \pmod{497} \equiv 256 \pmod{497} </math>。

第3步第3位为1，故令<math> R \leftarrow R \cdot x \text{ }(= b^5) \equiv 4 \cdot 256 \pmod{497} \equiv 30 \pmod{497} </math>；

令<math> x \leftarrow x^2 \text{ }(= b^8) \equiv 256^2 \pmod{497} \equiv 429 \pmod{497} </math>。

第4步第4位为1，故令<math> R \leftarrow R \cdot x \text{ }(= b^{13}) \equiv 30 \cdot 429 \pmod{497} \equiv 445 \pmod{497} </math>；

综上，<math>R</math>为<math>4^{13} \pmod{497} \equiv 445 \pmod{497}</math>，与先前算法中所得结果相同。

该算法时间复杂度为 $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]^{[失效链接]}

另见[编辑]

蒙哥马利算法，用于计算模很大时的余数。

参考资料[编辑]

↑ Weak Diffie-Hellman and the Logjam Attack. weakdh.org. [2019-05-03]. （原始内容存档于2021-03-29）.
↑ 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）.

[1] Weak Diffie-Hellman and the Logjam Attack. weakdh.org. [2019-05-03]. （原始内容存档于2021-03-29）.

[schneier96p244-2] Schneier 1996, p. 244.

[1]

[2]

查论编数论算法
素数测试	AKS APR（英语：Adleman–Pomerance–Rumely primality test） Baillie–PSW（英语：Baillie–PSW primality test）椭圆曲线（英语：Elliptic curve primality） Pocklington（英语：Pocklington primality test）费马卢卡斯（英语：Lucas primality test）卢卡斯-莱默 Lucas–Lehmer–Riesel（英语：Lucas–Lehmer–Riesel test）普罗斯 Pépin（英语：Pépin's test）二次Frobenius（英语：Quadratic Frobenius test） Solovay–Strassen（英语：Solovay–Strassen primality test）米勒-拉宾
素数生成（英语：Generating primes）	阿特金筛法（英语：Sieve of Atkin）埃拉托斯特尼筛法 Pritchard筛法（英语：Sieve of Pritchard） Sundaram筛法（英语：Sieve of Sundaram）轮式因数分解法（英语：Wheel factorization）
整数分解	连分数分解 (CFRAC)（英语：Continued fraction factorization） Dixon's（英语：Dixon's factorization method） Lenstra椭圆曲线 (ECM)（英语：Lenstra elliptic-curve factorization）欧拉因式分解法波拉德ρ算法（英语：Pollard's rho algorithm） p − 1（英语：Pollard's p − 1 algorithm） p + 1（英语：Williams's p + 1 algorithm）二次筛选法普通数域筛选法特殊数域筛选法 (SNFS)（英语：Special number field sieve）有理筛选法费马因式分解法（英语：Fermat's factorization method） Shanks二次形式（英语：Shanks's square forms factorization）试除法秀尔算法
乘法算法	古埃及乘算（英语：Ancient Egyptian multiplication）长乘法卡拉楚巴算法图姆-库克算法颂哈吉-施特拉森算法富尔算法（英语：Fürer's algorithm）
欧几里德除法除法算法	二进制（英语：Binary division）倍块法（英语：Chunking (division)） Fourier（英语：Fourier division） Goldschmidt（英语：Goldschmidt division） Newton-Raphson（英语：Newton–Raphson division）长除法短除法 SRT
离散对数	大步小步算法波拉德ρ算法 Pollard kangaroo（英语：Pollard's kangaroo algorithm） Pohlig–Hellman（英语：Pohlig–Hellman algorithm） Index calculus（英语：Index calculus algorithm） Function field sieve（英语：Function field sieve）
最大公因数	二进制最大公因数算法（英语：Binary GCD algorithm）辗转相除法扩展欧几里得算法 Lehmer's（英语：Lehmer's GCD algorithm）
二次剩余	Cipolla（英语：Cipolla's algorithm） Pocklington's（英语：Pocklington's algorithm） Tonelli–Shanks（英语：Tonelli–Shanks algorithm） Berlekamp（英语：Berlekamp–Rabin algorithm） Kunerth（英语：Kunerth's algorithm）
其他算法	Chakravala（英语：Chakravala method） Cornacchia（英语：Cornacchia's algorithm）整数关系（英语：Integer relation algorithm）（LLL（英语：Lenstra–Lenstra–Lovász lattice basis reduction algorithm）；KZ（英语：Korkine–Zolotarev lattice basis reduction algorithm））平方求幂整数平方根模幂运算蒙哥马利算法 Schoof（英语：Schoof's algorithm）特拉亨伯格系统（英语：Trachtenberg system）
斜体表示该算法只适用于特殊形式的数字

模幂

目录

直接算法[编辑]

空间优化[编辑]

从右到左二位算法[编辑]

伪代码[编辑]

Lua实现[编辑]

软件实现[编辑]

另见[编辑]

参考资料[编辑]

外部链接[编辑]

导航菜单

模幂

直接算法[编辑]

空间优化[编辑]

从右到左二位算法[编辑]

伪代码[编辑]

Lua实现[编辑]

软件实现[编辑]

另见[编辑]

参考资料[编辑]

外部链接[编辑]

导航菜单

搜索