快速冪 (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)$。

小結：一句話記住它

「快速冪是『倍增』的藝術。透過反覆平方底數，她以指數級速度穿越指數，將不可能的計算任務瞬間完成。」