快速幂

快速幂（模幂运算）在 $O(\log b)$ 次乘法内计算 $a^b\bmod m$，是同余算术中最基本的算法：素性检验、大数分解、离散对数问题等数论算法的内层循环都以模幂为原子操作。

算法

把 $b$ 写成二进制 $b=\sum_i b_i2^i$（$b_i\in\{0,1\}$），由

$$a^b\equiv\prod_{i:\,b_i=1}a^{2^i}\pmod m$$

逐位平方并累积：从 $a^{2^0}=a$ 出发，每步平方得 $a^{2^{i+1}}=(a^{2^i})^2$；若 $b_i=1$ 则乘入结果。

复杂度与正确性

• 模乘次数 $O(\log b)$（至多 $2\lfloor\log_2 b\rfloor$ 次），远优于逐次相乘的 $O(b)$
• 正确性由同余的乘法兼容性保证：$(x\bmod m)(y\bmod m)\equiv xy\pmod m$，中间值始终保持小于 $m^2$

指数约化

若 $\gcd(a,m)=1$，可用欧拉函数先约化指数：$a^b\equiv a^{b\bmod\varphi(m)}\pmod m$；一般情形先除以 $\gcd(a,m)$ 再约化。

示例

计算 $3^{25}\bmod7$：$25=(11001)_2$，$3^{1}=3$，$3^{2}\equiv2$，$3^{4}\equiv4$，$3^{8}\equiv2$，$3^{16}\equiv4$，故

$$3^{25}=3^{16}\cdot3^{8}\cdot3^1\equiv4\cdot2\cdot3=24\equiv3\pmod7$$

直接验证：$3$ 是模 $7$ 的原根，阶为 $6$，$3^{25}=(3^6)^4\cdot3\equiv3\pmod7$。

应用

模幂是一切模算术算法的基石：素性检验中的 $a^{n-1}\bmod n$、RSA 等公钥密码的加密解密、离散对数问题的群运算以及Shor算法的量子模幂都直接调用它。