快速幂

定义

快速幂(Binary Exponentiation,又称平方求幂)是在 O(log n) 次乘法内计算 aⁿ 的算法,思想是反复平方:aⁿ = (a²)^(n/2)(n 为偶数)或 a·aⁿ⁻¹(n 为奇数)。

原理

把指数 n 写成二进制,从低位到高位扫描:维护底数的连续平方,遇到二进制位为 1 时把当前平方值乘入结果。迭代实现只需常数额外空间。与取模结合即为快速模幂,每步乘法后取模防止溢出。

应用

RSA、Diffie-Hellman 等公钥密码的核心运算就是大数模幂;Miller-Rabin 素性测试、离散对数相关计算也依赖它。把"乘法"换成矩阵乘法即得矩阵快速幂,可在 O(log n) 时间求斐波那契数列等线性递推;更一般地,该技巧适用于任何满足结合律的运算。

说明

密码学实现中需注意恒定时间执行,否则平方-乘的分支差异可能泄露私钥(时序侧信道攻击)。