快速幂 (Binary Exponentiation)

引言：万亿步的问题

假设你需要计算 $3^{1,000,000,000,000}$ （3 的 1 万亿次方）。

• 朴素循环： 执行 3 * 3 * 3... 一万亿次。这需要耗费极长的时间。
• 快速幂： 只需约 40 步 就能算出结果。

这个算法是现代密码学（RSA, Diffie-Hellman）的基石，在这些领域中，对巨大的数字进行取模幂运算是标准操作。

算法要解决什么问题？

• 输入： 底数 $a$，指数 $n$，通常还有一个模数 $m$。
• 输出： $(a^n) \% m$。
• 承诺： 使用 $O(\log n)$ 次乘法而不是 $O(n)$ 次来计算结果。

核心思想 (直觉版)

利用指数的二进制表示。 $3^{10} = 3^{(1010)_2} = 3^8 \cdot 3^2$。 与其乘 3 十次，我们可以：

1. 计算 $3^1 = 3$。
2. 平方得到 $3^2 = 9$。
3. 平方得到 $3^4 = 81$。
4. 平方得到 $3^8 = 6561$。
5. 根据 10 的二进制位，组合我们需要的部分（$3^8$ 和 $3^2$）。

算法是如何工作的？

1. 初始化 result = 1。
2. 当 $n > 0$ 时：
   • 如果 $n$ 是奇数（最后一位是 1），将 result 乘以当前底数 $a$。
   • 将底数平方 ($a = a \cdot a$)。
   • 将 $n$ 除以 2（右移一位）。

典型业务场景

• ✅ 密码学： RSA 加密需要计算 $C = M^e \pmod N$，其中 $e$ 非常大。
• ✅ 矩阵幂： 通过矩阵快速幂，在 $O(\log n)$ 时间内计算第 $n$ 个斐波那契数。
• ✅ 组合数学： 计算模逆元 ($a^{p-2} \pmod p$) 以求解组合数 ${n \choose k}$。

代码演示 (TypeScript)

function modPow(base: bigint, exp: bigint, mod: bigint): bigint {
    let result = 1n;
    base = base % mod;

    while (exp > 0n) {
        // 如果指数是奇数，乘到结果里
        if (exp % 2n === 1n) {
            result = (result * base) % mod;
        }
        // 底数平方
        base = (base * base) % mod;
        // 指数减半
        exp = exp / 2n;
    }
    return result;
}

性能与复杂度总结

• 时间： $O(\log n)$。
• 空间： $O(1)$。

小结：一句话记住它

“快速幂是‘倍增’的艺术。通过反复平方底数，它以指数级速度穿越指数，将不可能的计算任务瞬间完成。”