模幂

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

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

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

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

$c=b^{e}modm=d^{-e}modm$，其中 $e<0$且$b\cdot d\equiv 1(\mathrm{mod}m)$。

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

直接算法

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

$c\equiv 4^{13}(\mathrm{mod}497)$

可用计算器算得4¹³结果为67,108,864，模除497，可得Template:Math等于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$，以下两个等式是等价的Template:Broken anchor：

$cmodm=(a\cdot b)modm$

$cmodm=[(amodm)\cdot (bmodm)]modm$

算法如下：

1. 令$c=1$，$e^{\prime }=0$。
2. $e^{\prime }$自增1。
3. 令$c=(b\cdot c)modm$.
4. 若$e^{\prime }<e$，则返回第二步；否则，$c$即为$c\equiv b^e(\mathrm{mod}m)$。

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

• $e^{\prime }=1\cdot c=(1\cdot 4)mod497=4mod497=4$
• $e^{\prime }=2\cdot c=(4\cdot 4)mod497=16mod497=16$
• $e^{\prime }=3\cdot c=(16\cdot 4)mod497=64mod497=64$
• $e^{\prime }=4\cdot c=(64\cdot 4)mod497=256mod497=256$
• $e^{\prime }=5\cdot c=(256\cdot 4)mod497=1024mod497=30$
• $e^{\prime }=6\cdot c=(30\cdot 4)mod497=120mod497=120$
• $e^{\prime }=7\cdot c=(120\cdot 4)mod497=480mod497=480$
• $e^{\prime }=8\cdot c=(480\cdot 4)mod497=1920mod497=429$
• $e^{\prime }=9\cdot c=(429\cdot 4)mod497=1716mod497=225$
• $e^{\prime }=10\cdot c=(225\cdot 4)mod497=900mod497=403$
• $e^{\prime }=11\cdot c=(403\cdot 4)mod497=1612mod497=121$
• $e^{\prime }=12\cdot c=(121\cdot 4)mod497=484mod497=484$
• $e^{\prime }=13\cdot c=(484\cdot 4)mod497=1936mod497=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\le i<n$），$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}(\text{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}modm$，其中$i$是循环执行次数。

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

首先，初始化结果$R$为1，并将Template:Math的值保存在变量$x$中：

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

第1步 第1位为1，故令$R\leftarrow R\cdot x(=b^1)$；

令$x\leftarrow x^2(=b^2)$。

第2步 第2位为0，故不给Template:Math赋值；

令$x\leftarrow x^2(=b^4)$。

第3步 第3位为1，故令$R\leftarrow R\cdot x(=b^5)$；

令$x\leftarrow x^2(=b^8)$。

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

这是最后一步，所以不需要对Template:Math求平方。

综上，$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(\mathrm{mod}497)\equiv 4(\mathrm{mod}497)$；

令$x\leftarrow x^2(=b^2)\equiv 4^2\equiv 16(\mathrm{mod}497)$。

第2步 第2位为0，故不给Template:Math赋值；

令$x\leftarrow x^2(=b^4)\equiv 16^2(\mathrm{mod}497)\equiv 256(\mathrm{mod}497)$。

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

令$x\leftarrow x^2(=b^8)\equiv 256^2(\mathrm{mod}497)\equiv 429(\mathrm{mod}497)$。

第4步 第4位为1，故令$R\leftarrow R\cdot x(=b^{13})\equiv 30\cdot 429(\mathrm{mod}497)\equiv 445(\mathrm{mod}497)$；

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

该算法时间复杂度为Template:MathexponentTemplate:Math。指数exponent值较大时，这种算法与前两种Template:MathexponentTemplate:Math算法相比具有明显的速度优势。例如，如果指数为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] Template:Wayback
• .NET框架的BigInteger类的ModPow()方法
• Java的java.math.BigInteger类的Template:Javadoc:SE方法
• Perl的Math::BigInt模块的bmodpow()方法[2] Template:Wayback
• Raku内置的expmod例程
• Go的big.Int类的Exp()（求幂）方法[3] Template:Wayback
• PHP的BC Math库的bcpowmod()函数[4] Template:Wayback
• GNU多重精度运算库（GMP）的mpz_powm()函数[5] Template:Wayback
• FileMaker Pro的@PowerMod()函数（以1024位RSA加密为例）
• Ruby的openssl包的OpenSSL::BN#mod_exp方法[6] Template:Wayback
• HP Prime计算器的CAS.powmod()函数[7]Template:Dead link

另见

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

外部链接

• Template:Cite book
• Paul Garrett, Fast Modular Exponentiation Java Applet Template:Wayback
• Template:Cite journal