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

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

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

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

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

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

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

: c\equiv 4^{13}\pmod{497}

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

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

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

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

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

: c \bmod m=(a\cdot b) \bmod m
: c \bmod m=[(a \bmod m)\cdot (b \bmod m)]\bmod m

算法如下：

令c=1，e'=0。

e'自增1。

令c=(b\cdot c) \bmod m.

若e'，则返回第二步；否则，c即为c\equiv b^e \pmod{m}。

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

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

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

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

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

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

: e = \sum_{i=0}^{n-1} a_i 2^i

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

b^e的值可写作：

: 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即为：

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

伪代码
下述伪代码基于布魯斯·施奈爾所著《应用密码学》。其中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^{2^i} \bmod m，其中i是循环执行次数。

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

首先，初始化结果R为1，并将的值保存在变量x中：
: R \leftarrow 1 \, ( = b^0) \text{且 } x \leftarrow b .
: 第1步 第1位为1，故令 R \leftarrow R \cdot x \text{ }(= b^1) ；
:: 令 x \leftarrow x^2 \text{ }(= b^2) 。
: 第2步 第2位为0，故不给赋值；
:: 令 x \leftarrow x^2 \text{ }(= b^4) 。
: 第3步 第3位为1，故令 R \leftarrow R \cdot x \text{ }(= b^5) ；
:: 令 x \leftarrow x^2 \text{ }(= b^8) 。
: 第4步 第4位为1，故令 R \leftarrow R \cdot x \text{ }(= b^{13}) ；
:: 这是最后一步，所以不需要对求平方。
综上，R为b^{13}。

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

初始化：
: R \leftarrow 1 \, ( = b^0) 且 x \leftarrow b = 4 。
: 第1步 第1位为1，故令R \leftarrow R \cdot 4 \pmod {497} \equiv 4 \pmod{497} ；
:: 令 x \leftarrow x^2 \text{ }(= b^2) \equiv 4^2 \equiv 16 \pmod{497} 。
: 第2步 第2位为0，故不给赋值；
:: 令 x \leftarrow x^2 \text{ }(= b^4) \equiv 16^2 \pmod{497} \equiv 256 \pmod{497} 。
: 第3步 第3位为1，故令 R \leftarrow R \cdot x \text{ }(= b^5) \equiv 4 \cdot 256 \pmod{497} \equiv 30 \pmod{497} ；
:: 令 x \leftarrow x^2 \text{ }(= b^8) \equiv 256^2 \pmod{497} \equiv 429 \pmod{497} 。
: 第4步 第4位为1，故令 R \leftarrow R \cdot x \text{ }(= b^{13}) \equiv 30 \cdot 429 \pmod{497} \equiv 445 \pmod{497} ；

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

该算法时间复杂度为exponent。指数exponent值较大时，这种算法与前两种exponent算法相比具有明显的速度优势。例如，如果指数为220 = 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()（求幂）函数[https://docs.python.org/library/functions.html#pow]
• .NET框架的BigInteger类的[http://msdn.microsoft.com/en-us/library/system.numerics.biginteger.modpow%28v=vs.100%29.aspx#pow ModPow()]方法
• Java的java.math.BigInteger类的方法
• Perl的Math::BigInt模块的bmodpow()方法[http://perldoc.perl.org/Math/BigInt.html#bmodpow%28%29]
• Raku内置的expmod例程
• Go的big.Int类的Exp()（求幂）方法[http://golang.org/pkg/big/#Int.Exp]
• PHP的BC Math库的bcpowmod()函数[http://www.php.net/manual/en/function.bcpowmod.php]
• GNU多重精度运算库（GMP）的mpz_powm()函数[http://gmplib.org/manual/Integer-Exponentiation.html]
• FileMaker Pro的[http://www.briandunning.com/cf/1482 @PowerMod()]函数（以1024位RSA加密为例）
• Ruby的openssl包的OpenSSL::BN#mod_exp方法[http://ruby-doc.org/stdlib-trunk/libdoc/openssl/rdoc/OpenSSL/BN.html#method-i-mod_exp]
• HP Prime计算器的CAS.powmod()函数[http://h20628.www2.hp.com/km-ext/kmcsdirect/emr_na-c04120022-1.pdf]

另见

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

参考资料
外部链接
*

• Paul Garrett, [http://www.math.umn.edu/~garrett/crypto/a01/FastPow.html Fast Modular Exponentiation Java Applet]

*