2002 - AKS 質數檢驗#

案件摘要#

2002 年 8 月，印度 IIT Kanpur 的教授 Agrawal 與兩位大學生 Kayal、Saxena 發表論文《PRIMES is in P》，給出第一個確定性多項式時間質數檢驗演算法（AKS）。這樁 30 年懸案——「質數檢驗是否在 P 中」——就此偵破，且由本科生完成，震驚學界。

前因 -- 為什麼會有這個案子#

17 世紀：Fermat 小定理給出質數的必要條件：若 \(p\) 為質數且 \(\gcd(a, p) = 1\) ，則

\[ a^{p-1} \equiv 1 \pmod{p} \]

但其逆不真（Carmichael 數如 \(561 = 3 \times 11 \times 17\) 對所有 \(a\) 皆滿足）。 - 1976 年：Miller 提出確定性檢驗，但依賴「廣義 Riemann 假設（GRH）」。 - 1977 年：Rabin 將其改良為不依賴假設的機率式檢驗（Miller–Rabin），錯誤率 \(\leq 4^{-k}\) 。 - 1980 年：Solovay–Strassen 提出另一機率式檢驗（基於 Euler 判別式 \(\left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod p\) ），錯誤率 \(\leq 2^{-k}\) 。 - 疑案本質：機率式檢驗極快但「可能說謊」；確定性檢驗（試除法 \(O(\sqrt{n})\) ）慢到不可用。「確定性 + 多項式」兩全其美的演算法是否存在？

線索與推理 -- 數學式、程式、理論#

1. 前代檢驗的數學#

Fermat 小定理（1640）：

\[ a^{p-1} \equiv 1 \pmod{p}, \quad \gcd(a,p)=1 \]

缺點：Carmichael 數會偽裝成質數。

Miller–Rabin（1977/1980）：將 \(p-1 = 2^s \cdot d\) （ \(d\) 奇數），檢驗：

\[ a^d \not\equiv 1 \pmod n \ \text{且} \ a^{2^r d} \not\equiv -1 \pmod n, \quad \forall\, 0 \le r < s \]

若對某 \(a\) 成立則 \(n\) 必為合數；機率式，錯誤率 \(\leq 4^{-k}\) 。

Solovay–Strassen（1980）：基於 Jacobi 符號：

\[ a^{(n-1)/2} \not\equiv \left(\frac{a}{n}\right) \pmod n \implies n \text{ 為合數} \]

2. AKS 定理（2002）#

定理（Agrawal–Kayal–Saxena）：存在確定性演算法，在 \(\tilde{O}(\log^6 n)\) 時間內判定 \(n\) 是否為質數。即：

\[ \text{PRIMES} \in \text{P} \]

（ \(\tilde{O}\) 忽略對數因子。原始版本為 \(\tilde{O}(\log^{12} n)\) ，經 Lenstra–Pomerance 等改良後降至 \(\tilde{O}(\log^6 n)\) 。）

3. AKS 條件的數學內容#

AKS 的核心是一條「多項式恆等式」判別法。若 \(n\) 為質數，則對任意整數 \(a\) ：

\[ (x+a)^n \equiv x^n + a \pmod{n} \]

因為二項式係數 \(\binom{n}{k} \equiv 0 \pmod n\) （ \(0 < k < n\) ）。其逆：若此恆等式對某 \(a\) 不成立，則 \(n\) 必為合數。

問題：直接展開 \((x+a)^n\) 需要 \(n\) 個係數，指數級。AKS 的妙手：在商環中模運算——取小整數 \(r\) ，對 \(x^r - 1\) 取模（即只保留次數 \(< r\) 的係數）：

\[ (x+a)^n \equiv x^n + a \pmod{x^r - 1,\ n} \]

這是「代數壓縮」：把指數級資訊壓進 \(r\) 個係數裡。AKS 證明存在適當的 \(r = O(\log^5 n)\) ，使得此條件對足夠多的 \(a\) 成立當且僅當 \(n\) 是質數的純冪或質數——再篩掉純冪即可。

演算法骨架： 1. 檢查 \(n = a^b\) （純冪）？若是，合數。 2. 找最小 \(r\) ，使 \(\text{ord}_r(n) > \log^2 n\) 。 3. 檢查 \(1 < \gcd(a, n) < n\) 對 \(a \le r\) （找出小因子）。 4. 對 \(a = 1, \dots, \lfloor \sqrt{\varphi(r)} \log n \rfloor\) 驗證 \((x+a)^n \equiv x^n + a \pmod{x^r-1,\ n}\) 。 5. 通過全部檢驗 ⟹ \(n\) 是質數。

4. 程式碼範例：簡化版 AKS 與 Miller–Rabin 對照#

import random

def is_perfect_power(n):
    for b in range(2, n.bit_length()):
        a = round(n ** (1 / b))
        if a ** b == n or (a + 1) ** b == n:
            return True
    return False

def aks_simplified(n):
    """簡化版 AKS：直接檢查多項式恆等式（未做 x^r-1 壓縮，僅教學用）"""
    if n < 2: return False
    if is_perfect_power(n): return False
    for a in range(1, min(n, 20)):          # 教學版只取少量 a
        coeffs = [1]
        for _ in range(n):                   # 二項式展開 (x+a)^n
            coeffs = [c1 + c2 for c1, c2 in
                      zip([0] + coeffs, coeffs + [0])]
        lhs = coeffs                         # (x+a)^n 的係數
        rhs = [1] + [0] * (n - 1) + [a]      # x^n + a 的係數
        if (lhs[0] % n != rhs[0] % n or
            (lhs[n] if n < len(lhs) else 0) % n != rhs[-1] % n):
            return False
        for k in range(1, n):                # 中間係數必為 0 mod n
            if coeffs[k] % n != 0:
                return False
    return True

def miller_rabin(n, k=10):
    """機率式：快但可能說謊，錯誤率 <= 4^-k"""
    if n < 2: return False
    for p in [2, 3, 5, 7, 11, 13]:
        if n % p == 0: return n == p
    d, s = n - 1, 0
    while d % 2 == 0: d //= 2; s += 1
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x in (1, n - 1): continue
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1: break
        else:
            return False
    return True

print(aks_simplified(101), miller_rabin(101))       # True True
print(aks_simplified(561), miller_rabin(561))       # False False（Carmichael 數）

對照表：

檢驗	時間	確定性	弱點
試除法	\(O(\sqrt{n})\)	確定	指數級（於輸入長度）
Fermat	\(\tilde{O}(\log^3 n)\)	機率	Carmichael 數
Solovay–Strassen	\(\tilde{O}(\log^3 n)\)	機率	錯誤率 \(2^{-k}\)
Miller–Rabin	\(\tilde{O}(\log^3 n)\)	機率	錯誤率 \(4^{-k}\) （GRH 下可確定）
AKS	\(\tilde{O}(\log^6 n)\)	確定	常數較大，實務上少用

結案 -- 後果與影響#

結案：PRIMES is in P，30 年懸案偵破。這是第一個「自然問題落入 P」的重大案例——此前已知的多項式演算法多是「問題本身的自然身份」，而質數檢驗是密碼學核心運算，地位特殊。
影響 1：理論上，RSA 的安全性不再能訴諸「質數產生可能不高效」——金鑰產生有確定性多項式保證（但分解仍難，故 RSA 仍安全）。
影響 2：實務上 Miller–Rabin 仍是最快選擇（AKS 常數太大），但 AKS 提供了「最壞情況保證」的理論基準線。
影響 3：證明技術啟發後續研究：AKS 用的「代數壓縮 + 恆等式驗證」與 GCT、IP = PSPACE 的代數技巧一脈相承。
影響 4：本科生 Neeraj Kayal、Nitin Saxena 一戰成名，後皆任職於 Microsoft Research 與頂尖學府，成為複雜性理論中堅。
影響 5：確立「多項式恆等式測試（PIT）」為重要工具——PIT 本身是另一個 P vs BPP 型懸案（AKS 是 PIT 的特例之確定解）。

關鍵人物與文獻#

Manindra Agrawal（IIT Kanpur 教授，指導者）。
Neeraj Kayal、Nitin Saxena（當時為大學生，後為知名複雜性理論學家）。
Gary Miller（1976）、Michael Rabin（1980）、Solovay–Strassen（1980）：前代檢驗。
文獻：M. Agrawal, N. Kayal, N. Saxena, "PRIMES is in P", Annals of Mathematics 160(2), 2004（2002 年 8 月首度發表於 IIT Kanpre 網站）；原本的 2002 預印本即獲 2006 年 Gödel Prize。
延伸：Lenstra–Pomerance 的改良版 AKS（ \(\tilde{O}(\log^6 n)\) ）。