1994 - Shor 演算法#

案件摘要#

1994 年，Bell 實驗室的 Peter Shor 發表《Algorithms for Quantum Computation: Discrete Logarithms and Factoring：量子電腦可以在多項式時間內分解大數與解離散對數——RSA、Diffie–Hellman、ElGamal、ECC 全部被判死刑**。這是密碼學史的地震：所有現代公鑰密碼的難解假設在量子模型下失效，催生了後量子密碼學（見 2017-後量子密碼學.md）。Shor 的演算法也是量子計算從「玩具」變成「國安議題」的分水嶺。

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

1994 年量子計算的狀態：Deutsch (1985) 的量子圖靈機、Feynman (1982) 的量子模擬構想、Deutsch–Jozsa (1992) 與 Simon (1994) 的早期量子算法——都是「量子快於經典」的示範，但沒有實用價值。Shor 的問題：量子電腦能否解決一個「重要問題」？

RSA 的安全依賴大數分解難（見 1977-RSA.md）；DH/ElGamal 依賴離散對數難（見 1976-DiffieHellman金鑰交換.md）。經典計算下這些問題被認為難（次指數但不可行）——若量子多項式時間可解，密碼學的地基崩塌。

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

關鍵：週期性與傅立葉#

Shor 的洞察：分解與離散對數都可以化為找函數的週期：

分解化為週期：隨機選 \(a\) ，函數 \(f(x) = a^x \bmod n\) 是週期函數（週期 \(r\) 使 \(a^r \equiv 1 \pmod n\) ）。找到 \(r\) （偶數且 \(a^{r/2} \ne -1\) ）後：

\[ a^r \equiv 1 \implies (a^{r/2} - 1)(a^{r/2} + 1) \equiv 0 \pmod n \]

—— \(n\) 的因數出現在 \(\gcd(a^{r/2} \pm 1, n)\) 中！分解問題化為找 \(f\) 的週期。

找週期是量子電腦的強項：經典計算找 \(f\) 的週期需要 \(O(n)\) 次求值；量子計算用量子傅立葉變換（QFT）在疊加態上一次求值全部， \(O(\log^2 n)\) 步。

Shor 演算法#

1. 隨機選 a，gcd(a, n) != 1 則已得因數（機率極小）
2. 準備疊加態：1/sqrt(q) * Σ_x |x⟩|0⟩
3. 計算 f(x) = a^x mod n（量子求冪）：|x⟩|a^x mod n⟩
4. 量子傅立葉變換（QFT）於第一暫存器
5. 測量：得週期 r 的近似（連分數還原）
6. gcd(a^{r/2} ± 1, n) —— 因數！

複雜度： \(O((\log n)^3)\) ——多項式時間！

對照：經典數域篩法 \(\exp(O(\sqrt{\log n \log\log n}))\) ——次指數。2048 位元 RSA：經典需數十億年，量子（足夠大的電腦）需數小時。

量子傅立葉變換#

QFT 是經典 DFT 的量子版：

\[ QFT |x\rangle = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} e^{2\pi i xy/N} |y\rangle \]

量子加速的本質：經典 FFT 是 \(O(N \log N)\) （ \(N = 2^n\) 輸入），QFT 只用 \(O(n^2)\) 個閘——因為疊加態天然包含全部輸入，QFT 作用於整個疊加。但測量只得到一個樣本——需要疊加 + 週期性 + 連分數的配合才能提取週期。

偵探筆記：Shor 的推理鏈：分解 → 週期性 → 疊加態全體求值 → QFT 提取週期 → GCD 得因數。量子加速不來自「並行試所有答案」，而來自「週期函數的傅立葉結構 + 疊加態的同時求值」——這個洞見與 Simon 演算法（1994，Shor 的直接前身）一脈相承。

Grover 演算法（1996）#

另一個量子算法（Shor 的補充）：無結構搜尋的平方加速——

\[ \text{經典 } O(N) \to \text{量子 } O(\sqrt{N}) \]

密碼學影響：對稱密碼的金鑰搜尋（AES-128 的 \(2^{128}\) → 量子的 \(2^{64}\) ）——不是死刑，是金鑰長度加倍（AES-256 足夠）。與 Shor 的死刑（公鑰密碼）形成對照。

程式碼：Shor 演算法的經典模擬（小數）#

import random, math

def shor_classic(n):
    """小 n 的 Shor 演算法（經典部分模擬：量子週期查找用暴力代替）"""
    while True:
        a = random.randint(2, n - 1)
        g = math.gcd(a, n)
        if g != 1:
            return g, n // g                 # 直接得因數
        # 找 f(x) = a^x mod n 的週期 r（量子部分：此處暴力模擬）
        x, seen = 1, {}
        r = 0
        for i in range(1, n):
            x = x * a % n
            if x in seen:
                r = i - seen[x]              # 週期
                break
            seen[x] = i
        if r % 2 == 1: continue              # 週期須偶數
        if pow(a, r // 2, n) == n - 1: continue  # a^{r/2} != -1
        f1 = math.gcd(pow(a, r//2, n) - 1, n)
        f2 = math.gcd(pow(a, r//2, n) + 1, n)
        if 1 < f1 < n:
            return f1, n // f1
        if 1 < f2 < n:
            return f2, n // f2

random.seed(42)
for n in [15, 21, 35, 91]:
    print(f"分解 {n} = {shor_classic(n)}")
# 量子版把「找週期」從 O(n) 降到 O(log^2 n)——多項式時間分解

# Grover 的平方加速：AES-128 的金鑰搜尋 2^128 -> 2^64
print("Grover 演算法：無結構搜尋 O(N) -> O(sqrt(N))")

結案 -- 後果與影響#

密碼學的地震：RSA、DH、ElGamal、ECC 的難解假設在量子下失效——現代公鑰密碼需要後量子替代。
後量子密碼學：格密碼（LWE）、編碼密碼、多變量密碼——2017 年 NIST 競賽（見 2017-後量子密碼學.md）。
量子計算的國安地位：1994 年後量子計算從學術玩具變成情報機構的戰略投資——「先存後解」（harvest now, decrypt later）的威脅。
量子計算的譜系：Deutsch–Jozsa (1992) → Simon (1994) → Shor (1994) → Grover (1996)——量子算法的黃金年代。
理論意義：BQP（量子多項式時間）與 BPP 的關係——量子計算未推翻 Church–Turing 命題，但改變了複雜度（見 ../計算理論/README.md）。
現實進度：2024 年最快的量子電腦約千級物理位元——分解 RSA-2048 需數百萬級糾錯位元，尚遠。但威脅是確定的方向。

關鍵人物與文獻#

Peter Shor（1959–）：Algorithms for Quantum Computation... (1994, FOCS)；Shor 演算法
David Deutsch（1953–）：量子圖靈機 (1985)
Daniel Simon：Simon 演算法 (1994)——Shor 的直接前身
Lov Grover：Grover 演算法 (1996)
Feynman：量子模擬構想 (1982)
交叉參照：1977-RSA.md、1976-DiffieHellman金鑰交換.md、2017-後量子密碼學.md、../計算理論/README.md