2.3 模冪運算與費馬小定理#

概念說明#

計算 a^k mod m，最直覺的方法是先算出 a^k 再取模，但 a^k 可能大到天文數字（例如 2^(10^9) 有三億多個位數），根本算不動也不該算。模冪運算（modular exponentiation）的關鍵是「邊乘邊取模」：因為 (x·y) mod m = ((x mod m)·(y mod m)) mod m，所以在每步乘法後立刻縮小數值，過程中的數字永遠不超過 m²。

更聰明的是平方-相乘法（square-and-multiply）：把指數 k 寫成二進位，例如 a^13 = a^(1101₂) = a^8 · a^4 · a^1。從 a 開始反复平方（a, a², a⁴, a⁸, …），遇到指數的二進位該位是 1 就把當前的平方值乘進答案。這樣只需 O(log k) 次乘法，而不是 k−1 次。

這套技巧在密碼學裡無所不在：RSA 加解密、Diffie–Hellman 金鑰交換、ElGamal 加密，核心都是「模一個大質數的冪」。而保證這些系統正確性的基石之一是費馬小定理：若 p 是質數且 a 不是 p 的倍數，則

a^(p−1) ≡ 1 (mod p)

它有兩個重要用途：(1) 把大指數縮小，a^k mod p 可化為 a^(k mod (p−1)) mod p（當 p 不整除 a）；(2) 費馬質數測試——若存在 a 使 a^(p−1) ≢ 1 (mod p)，則 p 一定不是質數。這也是 2.1 節米勒–拉賓測試的前身。

演算法步驟#

快速冪（迭代版）： 1. 初始化 result = 1，base = a mod m。 2. 當 k > 0： - 若 k 的最低位元是 1（k 為奇數），result = (result × base) mod m。 - base = (base × base) mod m。 - k 右移一位（k = k >> 1）。 3. 回傳 result。

費馬質數測試： 1. 反複選取隨機的 a ∈ [2, p−2]。 2. 若 a^(p−1) mod p ≠ 1，回報「必為合成數」。 3. 若多次測試皆通過，則 p「可能是質數」。

Python 程式碼範例#

import random

def mod_pow(a, k, m):
    """平方-相乘法：計算 a^k mod m。Python 內建 pow(a, k, m) 功能相同"""
    result = 1
    a %= m
    while k > 0:
        if k & 1:              # 指數最低位是 1
            result = result * a % m
        a = a * a % m          # 反複平方
        k >>= 1
    return result

# 驗證正確性
print(mod_pow(2, 10, 1000))            # 24（1024 mod 1000）
print(pow(7, 128, 13) == mod_pow(7, 128, 13))

# 對比：笨方法 vs 快速冪的乘法次數差異（這裡比較執行差）
#笨方法要 999 次乘法才得 7^1000；快速冪只要約 10 次平方+幾次乘法
print(mod_pow(7, 1000, 65537))

# 費馬小定理示範：p 為質數時 a^(p-1) ≡ 1 (mod p)
p = 101
print(all(mod_pow(a, p - 1, p) == 1 for a in range(2, p)))

# 用費馬小定理縮小指數：7^1000 mod 101 = 7^(1000 mod 100) mod 101
print(mod_pow(7, 1000, 101), mod_pow(7, 1000 % 100, 101))   # 兩者相同

def fermat_test(n, trials=20):
    """費馬質數測試；注意會被卡邁克爾數騙過"""
    if n < 2:
        return False
    for _ in range(trials):
        a = random.randrange(2, n - 1)
        if mod_pow(a, n - 1, n) != 1:
            return False
    return True

print(fermat_test(2**61 - 1))   # True（梅森質數）

# 卡邁克爾數 561 = 3 × 11 × 17：費馬測試幾乎全過，但它是合成數
print(fermat_test(561))                 # True（被騙！）
print((3 - 1) * (11 - 1) * (17 - 1))    # lcm(2,10,16)=80 整除 560，因此騙過

複雜度分析#

平方-相乘法需要 O(log k) 次模乘法，每次模乘在固定寬度整數（如 64 位）上是常數時間，對超大整數則是小於 O(log m)² 位數的乘法成本。費馬測試做 t 輪就是 O(t · log n) 次模乘。要特別注意正確性的陷阱：費馬測試對卡邁克爾數（如 561、1105、1729、41041）會嚴重誤判——這類合成數 n 滿足對所有與 n 互質的 a 都有 a^(n−1) ≡ 1 (mod n)，因此單靠費馬定理無法辨識它們。米勒–拉賓測試（2.1 節）透過把 n−1 分解成 2^s·d 並檢查平方根鏈，徹底堵住這個漏洞。實務上，Python 內建 pow(a, k, m) 使用高度優化的 C 實作，速度遠超純 Python 版本，正式程式碼應直接使用內建函式。

練習#

寫出遞迴版的 mod_pow_rec(a, k, m)（用 a^k = a^(k//2)² × (a 若 k 為奇)），並與迭代版比對 1000 組隨機 (a, k, m) 的結果。
費馬小定理也能求模反元素：質數 p 下 a^(−1) ≡ a^(p−2) (mod p)。寫函式 inv_by_fermat(a, p)，並與 2.2 節擴展歐幾里得法的結果比對。
用「平方-相乘的乘法次數」做實驗：對 k = 10⁶、10¹²、10¹⁸，分別計算需要的乘法次數（約 log₂k），體會為什麼密碼學能承受 2048 位指數。