模幂运算

模幂运算计算 $a^{e}modm$，其中 $m\ge 1$、$e\ge 0$ 是整数。即使 $e$ 很大，也不必先造出巨大的整数 $a^e$：若 $x\equiv y(\mathrm{mod}m)$，则 $xz\equiv yz(\mathrm{mod}m)$，每次相乘后都可立即取余。反复平方把所需乘法次数从与 $e$ 同阶降到与其二进制位数同阶。

手算十三次幂

计算 $7^{13}mod11$。由 $13=8+4+1$，依次平方得 $7^2\equiv 5$、$7^4\equiv 5^2\equiv 3$、$7^8\equiv 3^2\equiv 9(\mathrm{mod}11)$。因此 $7^{13}\equiv 9\cdot 3\cdot 7=189\equiv 2(\mathrm{mod}11)$。每一步只保存余数，不保存 $7^{13}$ 本身。

从二进制展开到算法

维护不变量 $R{B}^q\equiv a^e(\mathrm{mod}m)$，起始 $R=1,B=amodm,q=e$。若 $q$ 为奇数，把一份 $B$ 乘进 $R$；随后令 $B\leftarrow B^{2}modm$、$q\leftarrow \lfloor q/2\rfloor$。若 $q=2k$，$B^{2k}=(B^2{)}^k$；若 $q=2k+1$，先把 $B$ 放进 $R$ 再用同一式，故不变量每轮保持。$q=0$ 时得到 $R\equiv a^e(\mathrm{mod}m)$。

Python 3

def pow_mod(base: int, exponent: int, modulus: int) -> int:
    if exponent < 0 or modulus < 1:
        raise ValueError("require exponent >= 0 and modulus >= 1")
    result = 1 % modulus
    base %= modulus
    while exponent:
        if exponent % 2:
            result = (result * base) % modulus
        base = (base * base) % modulus
        exponent //= 2
    return result

assert pow_mod(7, 13, 11) == 2
assert pow_mod(5, 0, 7) == 1
assert pow_mod(3, 4, 1) == 0

循环执行 $O(\log (e+1))$ 次模乘法；大整数乘法本身的位复杂度还取决于 $m$ 的位数。负指数需要 $a$ 在模 $m$ 下有逆元，即 $gcd(a,m)=1$，此页算法故意拒绝它。普通反复平方的执行分支会泄露指数位信息；密码协议应使用经过专门审查的实现，不能把上述教学代码直接当作安全加密库。

参考资料与相关词条

• MIT 6.042J：模运算与幂的习题。
• 相关：同余、欧几里得算法、中国剩余定理。