模幂

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

模幂运算是指求整数的次方被正整数所除得到的余数的过程，可用数学符号表示为。由的定义可得。

例如，给定，和，被13除得的余数。

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

 ，其中 且。

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

 直接算法 
计算模幂的最直接方法是直接算出，再把结果模除。假设已知，，以及，要求：



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

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

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

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

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




算法如下：

 令，。
 自增1。
 令.
 若，则返回第二步；否则，即为。

再以，，为例说明，算法第三步需要执行13次：















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

与第一种方法相同，这种算法需要的时间才能完成。但是，由于在计算过程中处理的数字比第一种算法小得多，因此计算时间至少减少了倍。

算法伪代码如下：
 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

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

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



此时的长度为位。对任意（），可取0或1任一值。由定义有。

的值可写作：



因此答案即为：



 伪代码 

下述伪代码基于布魯斯·施奈爾所著《应用密码学》Schneier 1996, p. 244.。其中base，exponent和modulus分别对应上式中的，和。

 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等于。在第三行代码中重复执行平方运算，会确保在每次循环结束时，变量base等于，其中是循环执行次数。

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

首先，初始化结果为1，并将的值保存在变量中：
 .
 第1步  第1位为1，故令；
 令。
 第2步  第2位为0，故不给赋值；
 令。
 第3步  第3位为1，故令；
 令。
 第4步  第4位为1，故令；
 这是最后一步，所以不需要对求平方。
综上，为。

以下计算的次方对497求模的结果。

初始化：
 且。
 第1步  第1位为1，故令；
 令。
 第2步  第2位为0，故不给赋值；
 令。
 第3步  第3位为1，故令；
 令。
 第4步  第4位为1，故令；

综上，为，与先前算法中所得结果相同。

该算法时间复杂度为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()（求幂）函数 
 .NET框架的BigInteger类的ModPow()方法
 Java的java.math.BigInteger类的方法
 Perl的Math::BigInt模块的bmodpow()方法 
 Raku内置的expmod例程
 Go的big.Int类的Exp()（求幂）方法 
 PHP的BC Math库的bcpowmod()函数 
 GNU多重精度运算库（GMP）的mpz_powm()函数 
 FileMaker Pro的@PowerMod()函数（以1024位RSA加密为例）
 Ruby的openssl包的OpenSSL::BN#mod_exp方法 
 HP Prime计算器的CAS.powmod()函数

 另见 

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

 参考资料 

 外部链接 


 Paul Garrett, Fast Modular Exponentiation Java Applet 


Category:密码算法
Category:数论算法
Category:同余
Category:带有伪代码示例的条目