快速幂算法：如何用 O(log n) 解决大数幂运算
引言
在计算机科学和密码学中，经常需要计算大数幂模运算（如 RSA 加密中的 m^d mod n）。当指数较大时，直接计算会导致性能问题和溢出。快速幂算法（Exponentiation by Squaring）通过二进制分解将时间复杂度从 O(n) 优化到 O(log n)，成为解决这类问题的关键技术。
算法原理
1. 二进制分解
将指数 e 转换为二进制形式：
5 (十进制) = 101 (二进制)
2. 平方累乘法
-
若当前二进制位为 1：结果乘以当前基数
-
每位处理完后：基数平方
-
每步执行模运算防止溢出
3. 数学表示
对于计算 a^e mod m：
-
递归式
ae={(ae/2)2if e is evena⋅(a(e−1)/2)2if e is odd
a^{e} =
\\begin{cases}
(a^{e/2})^2 & \\text{if } e \\text{ is even} \\\\
a \\cdot (a^{(e-1)/2})^2 & \\text{if } e \\text{ is odd}
\\end{cases}
ae={(ae/2)2a⋅(a(e−1)/2)2if e is evenif e is odd -
二进制表示指数形式的递推式
baseexp % mod=baseen−1,⋅⋅⋅,e2,e1,e0 % mod=((baseen−1<<n−1 % mod) ∗ ⋅⋅⋅∗ (baseel<<1 % mod) ∗ (basee0<<0 % mod)) % mod
base^{exp} \\text{ }\\% \\text{ } mod =base^{e_{n-1},\\cdot\\cdot\\cdot,e{_2},e{_1},e{_0}} \\text{ }\\% \\text{ } mod\\\\
=((base^{e_{n-1} << n-1}\\text{ }\\%\\text{ }mod) \\text{ }* \\text{ }\\cdot\\cdot\\cdot* \\text{ }(base^{e_{l} << 1}\\text{ } \\%\\text{ } mod) \\text{ }* \\text{ }(base^{e_{0} << 0} \\text{ }\\% \\text{ }mod ))\\text{ }\\% \\text{ }mod
baseexp % mod=baseen−1,⋅⋅⋅,e2,e1,e0 % mod=((baseen−1<<n−1 % mod) ∗ ⋅⋅⋅∗ (baseel<<1 % mod) ∗ (basee0<<0 % mod)) % mod
而baseibase^{i} % modbasei的结果，是逐渐翻倍的关系，即base2=(base1)2,base4=(base2)2base^{2} =(base^{1})^{2}, base^{4} = (base^{2})^{2}base2=(base1)2,base4=(base2)2
算法实现
Python 实现
def fast_power(base, exponent, modulus):
result = 1
base = base % modulus # 初始取模
while exponent > 0:
if exponent & 1: # 当前位为1
result = (result * base) % modulus
base = (base * base) % modulus # 基数平方
exponent >>= 1 # 右移一位
return result
C++ 实现
long fastPower(long base, long exponent, long modulus) {
long result = 1;
base = base % modulus;
while (exponent > 0) {
if (exponent & 1)
result = (result * base) % modulus;
base = (base * base) % modulus;
exponent >>= 1;
}
return result;
}
计算示例
示例 1：计算 3^5 mod 7
输出结果：5
示例 2：RSA 签名计算
m = 23547 # 消息
d = 132111 # 私钥
n = 824737 # 模数
signature = fast_power(m, d, n) # 输出：266749
复杂度分析
| 时间复杂度 | O(log n) | 指数每次循环减半 |
| 空间复杂度 | O(1) | 仅需常数级存储空间 |
| 性能提升 | 指数级 | 相比朴素算法 O(n) 显著优化 |
应用场景
密码学领域
- RSA 加密/解密
- 数字签名
- Diffie-Hellman 密钥交换
计算优化
- 大数模运算（如组合数计算）
- 动态规划状态转移优化
- 素数测试（Miller-Rabin算法）
总结
核心优势
算法意义
快速幂算法体现了“分治”思想的核心价值：
