模幂运算与快速幂:a 的 b 次方 mod m 是怎么算快的

模幂运算就是算 a 的 b 次方对 m 取余,写作 a^b mod m。它看上去只是三个数的小练习,却是 RSA、Diffie-Hellman 密钥交换、Miller-Rabin 素性测试这些公钥密码方案最里层的那一步。下面我把它拆开讲清楚:为什么不能傻算,快速幂怎么把步数砍下来,以及它真正用在哪。

为什么不能先算 a^b 再取模

最直觉的写法是:先把 a^b 算出来,再对 m 取余。问题是 a^b 涨得太快。光是 7^256 就已经有 200 多位数字,而一个真实的 RSA 指数算出来的数,位数比宇宙里的原子还多,任何机器都装不下,内存先爆掉。

诀窍在于:余数运算可以提前做,不必等到最后。乘法和取模满足 (x · y) mod m = ((x mod m) · (y mod m)) mod m。也就是说,每乘一步就立刻对 m 取一次模,中间结果永远小于 m,体积始终被压住。2048 位的 RSA 运算全程只占几百字节,正是靠这一点。

平方乘法:把指数级降成对数级

就算每步都取模,如果还是老老实实把底数自乘 b 次,b 是 65537 时就要乘六万多次。快速幂(也叫平方乘法,square-and-multiply)换了个思路:把指数写成二进制,反复平方。

这里给一个具体的复杂度对比。要算 a^13,13 的二进制是 1101。先靠平方依次得到 a、a^2、a^4、a^8,再把二进制位为 1 的那几项乘起来:a^8 · a^4 · a^1 = a^13。一共只需要大约 log2(b) 步,而不是 b 步。指数 65537 因此约 17 次平方就跑完,而不是乘 65537 次,从线性级直接降到对数级。位数越大,这个差距越夸张。

一个真实的输入输出例子

拿 3^200 mod 50 来走一遍。直接算 3^200 会得到一个 96 位的天文数字,但模幂运算用平方乘法逐位处理,每步都对 50 取模,最后落在 41。也就是说 3^200 mod 50 = 41。你不需要拼出那个 96 位的怪物,过程里出现的数字始终不超过两位数与中间乘积的范围。

我自己第一次写 modPow 时栽在一个经典坑上:平方之后忘了立刻取模,小数据测试全过,一上大输入就溢出错乱。后来把同样的底数、指数、模数粘进 模幂运算计算器 拿到已知正确答案,再打开分步视图逐一对照中间平方值,才精确定位到是哪一步开始岔开的。分步视图把每次平方都打出来,调试时比盯着公式有用得多。

它在密码学里到底用在哪

模幂运算是 RSA 的核心:加密是 c = m^e mod n,解密是 m = c^d mod n,两边都是一次模幂。Diffie-Hellman 密钥交换让双方各算一次 g^私钥 mod p,得到可以公开的值,再各自取对方的值做一次模幂,落到同一个共享密钥上。挑 RSA 大质数所用的 Miller-Rabin 素性测试,底子也是反复做模幂。

这些方案的安全性,正建立在模幂"正着算很便宜、倒着推很难"这条不对称上:给你 g、p 和 g^a mod p,想反推出私钥 a 就是离散对数难题,目前没有快速解法。

负指数与模逆元

有时你会想算 a 的负次方对 m 取模。这需要先求模逆元:a 模 m 的逆元是满足 a · x ≡ 1 (mod m) 的那个 x,只有当 a 与 m 互质(gcd 为 1)时才存在,通常用扩展欧几里得算法求出。判断互质这一步,可以先用 质因数分解工具 把两个数拆开看有没有公共因子。拿到逆元后,a^(-b) mod m 就等于 (a^(-1))^b mod m。比如 3 模 11 的逆元是 4,于是 3^(-2) mod 11 = 4^2 mod 11 = 16 mod 11 = 5。如果 gcd 不为 1,逆元不存在,负指数无定义,这时正确的做法是报错,而不是编一个数出来。

小结

模幂运算的全部精髓就两条:每步取模让中间值不膨胀,平方乘法让步数从 b 降到 log2(b)。理解了这两点,就理解了为什么现代公钥密码能在你手机上瞬间完成,而攻击者却要面对天文级的计算量。想动手验算 RSA 的某一步,或核对自己代码里的快速幂,直接把数填进计算器试一遍最快。

---

Made by Toolora · Updated 2026-06-13