模幂

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

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

例如，给定b = 5，e = 3和m = 13，5³ = 125被13除得的余数c = 8。

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

c = b^e mod m = d^−e mod m，其中 e < 0且b ⋅ d ≡ 1 (mod m)。

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

直接算法

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

c ≡ 4¹³ (mod 497)

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

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

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

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

内存优化

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

c mod m = (a ⋅ b) mod m

c mod m = [(a mod m) ⋅ (b mod m)] mod m

算法如下：

1. 令c = 1，e′ = 0。
2. e′自增1。
3. 令c = (b ⋅ c) mod m.
4. 若e′ < e，则返回第二步；否则，c即为c ≡ b^e (mod m)。

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

• e′ = 1. c = (1 ⋅ 4) mod 497 = 4 mod 497 = 4.
• e′ = 2. c = (4 ⋅ 4) mod 497 = 16 mod 497 = 16.
• e′ = 3. c = (16 ⋅ 4) mod 497 = 64 mod 497 = 64.
• e′ = 4. c = (64 ⋅ 4) mod 497 = 256 mod 497 = 256.
• e′ = 5. c = (256 ⋅ 4) mod 497 = 1024 mod 497 = 30.
• e′ = 6. c = (30 ⋅ 4) mod 497 = 120 mod 497 = 120.
• e′ = 7. c = (120 ⋅ 4) mod 497 = 480 mod 497 = 480.
• e′ = 8. c = (480 ⋅ 4) mod 497 = 1920 mod 497 = 429.
• e′ = 9. c = (429 ⋅ 4) mod 497 = 1716 mod 497 = 225.
• e′ = 10. c = (225 ⋅ 4) mod 497 = 900 mod 497 = 403.
• e′ = 11. c = (403 ⋅ 4) mod 497 = 1612 mod 497 = 121.
• e′ = 12. c = (121 ⋅ 4) mod 497 = 484 mod 497 = 484.
• e′ = 13. c = (484 ⋅ 4) mod 497 = 1936 mod 497 = 445.

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

与第一种方法相同，这种算法需要O(e)的时间才能完成。但是，由于在计算过程中处理的数字比第一种算法小得多，因此计算时间至少减少了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 

从右到左二位算法

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

首先把e表示成二进制，即：

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

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

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}}}$ 

因此答案c即为：

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

伪代码

下述伪代码基于布魯斯·施奈爾所著《应用密码学》^[2]。其中base，exponent和modulus分别对应上式中的b，e和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等于b。在第三行代码中重复执行平方运算，会确保在每次循环结束时，变量base等于b²ⁱ mod m，其中i是循环执行次数。

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

首先，初始化结果${\displaystyle R}$ 为1，并将b的值保存在变量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求平方。

综上，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}}}$ ；

综上，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）.