3.2 離散對數#

概念說明#

選定質數 p 與其原根（primitive root）g——即 g 的冪可以生成所有非零餘數 {1, 2, …, p−1}——則對任何 y ∈ [1, p−1]，存在唯一的 x ∈ [0, p−2] 滿足

y ≡ g^x (mod p)

求 x 的問題叫離散對數（discrete logarithm）。直觀類比：連續世界裡 log₂8 = 3，離散世界裡「3^x ≡ 17 (mod 101) 的 x 是幾？」兩者形式相同，但離散版因為取模的關係把「冪運算容易、反運算困難」的不對稱性放大到了密碼學級別。

為什麼要特意提離散對數？因為模冪容易、離散對數難運算「快到秒級」，反之沒有已知的多項式時間演算法——最好的經典演算法是亞指數級的指數積分式（index calculus）方法，但對足夠大的質數仍不可行。這種單向（one-way）性質正是下列協定的安全核心：

Diffie–Hellman 金鑰交換：雙方公開 g^a、g^b，各自用私密指數算出 g^(ab)，偷聽者只看得到 g^a、g^b，若無法解離散對數就得不到 g^(ab)。
ElGamal 加密：私鑰 a、公鑰 g^a，加密本質是乘上一次性冪 g^(ab)。

利用 Baby-Step Giant-Step（下文的 BSGS）可以把離散對數的暴力 O(1) 次比較優化到約 2√p 次運算，是理解其他更複雜指數型演算法的基礎。

演算法步驟#

解 g^x ≡ h (mod p) 的 Baby-Step Giant-Step：

令 n = p − 1（循環群大小），m = ⌈√n⌉。
Baby 步：對 j = 0..m−1，計算 h · g^(−j)（等價於 h · g^(n−j)），存進雜湊表「值 → j」。
Giant 步：對 i = 0..m−1，計算 g^(i·m) mod p；若這個值出現在雜湊表（記為 j），則 x = i·m + j 即為解。若都不相符，則無解（或 g 不是原根）。

原理：任何 x 都能寫成 x = i·m + j（商 i 與餘數 j），嬰步固定 j 補 h 邊，巨步以 m 為大步幅掃描，兩波相遇即得答案。

Python 程式碼範例#

import math
from sympy import primitive_root, isprime

def bsgs(g, h, p):
    """解 g^x ≡ h (mod p)，回傳最小的非負 x；無解回 None"""
    n = p - 1                      # 質數模的群階
    m = math.isqrt(n - 1) + 1
    # Baby steps: h * g^j for j in [0, m)
    table = {}
    e = h % p
    for j in range(m):
        table[e] = j
        e = e * g % p
    # Giant steps: g^(im)
    factor = pow(g, m, p)
    gamma = 1
    for i in range(m):
        if gamma in table:
            j = table[gamma]
            if pow(g, i * m + j, p) == h % p:   # 防碰撞誤判
                return i * m + j
        gamma = gamma * factor % p
    return None

p = 101
g = primitive_root(p)                     # sympy 找原根
h = 17
x = bsgs(g, h, p)
print(f"g={g}, h={h}, x={x}")
print(pow(g, x, p) == h)                  # True

# 隨機大範圍驗證（質數模）
p = 2**61 - 1
g = 7
h = pow(g, 987654321, p)
print(bsgs(g, h, p) == 987654321 % (p - 1))   # True

# 展示單向性：模冪快、離散對數慢
import time

p = 2**61 - 1
g = 7
x = 12345678901234567
t0 = time.perf_counter()
for _ in range(1000):
    pow(g, x, p)                         # 1000 次模冪，毫秒級
t1 = time.perf_counter() - t0
print(f"1000 次模冪耗時 {t1*1000:.1f} ms")

t0 = time.perf_counter()
bsgs(g, pow(g, x, p), 2**61 - 1)          # 只解 1 次離散對數
t1 = time.perf_counter() - t0
print(f"1 次離散對數耗時 {t1*1000:.1f} ms")   # 約幾百 ms 起，且隨 p 增大暴增

複雜度分析#

BSGS 需要 O(√p) 的時間與雜湊表空間——「時間→記憶體折衷」的經典示範。61 位元質數群約需 2^30.5 ≈ 1.5×10⁹ 步，電腦要花秒到分鐘級；256 位元的群則需 2^128 步——以全宇宙算力也跑不完，這正是密碼系統偏愛大質數的原因。若群階 n 的質因數都很小，Pohlig–Hellman 演算法可按下質因數各別解（用 BSGS 或暴力）再以 3.1 節 CRT 合併，安全等級取決於 n 的最大質因數；Pollard 的 ρ 演算法用 O(√n) 時間但僅 O(1) 空間。量子世界的 Shor 演算法理論上可用多項式時間解離散對數，這也是後量子密碼學研究的動機。實作細節：嬰步建表時不同的 j 可能撞出相同值（發生在 g 非原根、群階縮小時），本節程式在命中時以 pow 再次驗證，避免碰撞誤判。

練習#

求 5^x ≡ 73 (mod 101) 的 x，用你的 bsgs 求解後以 pow 驗證；再研究：5 是否為 101 的原根？若不是，結果有何不同？
實作暴力版 brute_dlog(g, h, p)（x 從 0 後依次試）與 bsgs 的執行時間比較，取 p = 10007、1000003、1000000007 觀察增長曲線是否約略符合 √p。
Diffie–Hellman 模擬：Alice 選 a、Bob 選 b（皆 20 位以上），在質數 p = 2**61−1 與 g = 5 下完成金鑰交換，驗證雙方算出相同的共享金鑰 g^(ab) mod p；再試著用 bsgs 破解 a，體會「痛快反向」的困難。