1994 - Shor 演算法#

案件摘要#

1994 年 Peter Shor 證明量子電腦可在多項式時間內分解大整數——直接威脅 RSA 密碼學的根基。演算法把質因數分解歸約為「週期尋找」，再用量子 Fourier 變換一次找出週期。這個結果引爆了量子電腦的全球投資，也催生了量子糾錯。

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

• 1977 年 RSA 密碼學問世：其安全性基於「大整數質因數分解在經典電腦上極難」。最好的經典演算法是數域篩法（general number field sieve），複雜度為次指數：

• 1985 年 Deutsch 提出通用量子電腦；1993 年 Simon 演算法顯示量子電腦可指數級加速「找週期/找隱藏異或」問題——Shor 看出這正是質因數分解的核心結構。
• 密碼學界的底線問題：如果量子電腦真的能造出來，全世界的公鑰金鑰系統還安全嗎？

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

步驟一：古典歸約到週期尋找#

要分解 \(N\) ，任選 \(a\) 與 \(N\) 互質（ \(\gcd(a,N)=1\) ）。考慮模指數函數的週期 \(r\) ：

若 \(r\) 是偶數且 \(a^{r/2} \not\equiv -1 \pmod{N}\) ，則

故 \(N\) 的質因數可由 \(\gcd(a^{r/2} \pm 1, N)\) 得到。例如 \(N=15,\ a=7\) ： \(7^2 \equiv 4,\ 7^4 \equiv 1 \pmod{15}\) ， \(r=4\) ， \(\gcd(7^2-1,15)=\gcd(48,15)=3\) ， \(\gcd(50,15)=5\) ，得 \(15 = 3 \times 5\) 。

問題只剩下：如何快速找 \(r\) ？

步驟二：量子 Fourier 變換（QFT）找週期#

1. 兩個暫存器：第一個疊加所有 \(x\) （ \(N \approx 2^n\) ）：

1. 計算 \(f(x) = a^x \bmod N\) ： \(\frac{1}{\sqrt{N}}\sum_x |x\rangle|a^x \bmod N\rangle\) （因 \(f\) 週期為 \(r\) ，測量第二暫存器後第一個塌縮為週期疊加 \(\sum_k |x_0 + kr\rangle\) ）。
2. QFT：

振幅在建構性干涉下集中於 \(k \approx \frac{mN}{r}\) （ \(m\) 為整數），測量得到 \(\frac{mN}{r}\) 的近似值，用連分數（continued fraction）演算法反推出 \(r\) 。

複雜度：多項式 vs 次指數#

Shor 演算法總複雜度：

（含 \(O(\log N)\) 次 QFT 與模指數的閘數。）與經典次指數 \(L_N[1/3, \ldots]\) 相比是指數級加速。這使分解 2048 位元 RSA 金鑰從「宇宙年齡級時間」降為多項式時間（在足夠大的容錯量子電腦上）。

Python 模擬：簡化版週期尋找（經典模擬量子部分）#

import numpy as np
from math import gcd, isclose
from fractions import Fraction

def shor_simulate(N, a, n_qubits):
    N_state = 2**n_qubits          # 量子暫存器大小
    # 步驟 1+2：疊加 + f(x)=a^x mod N（直接模擬測量後的週期結構）
    # 模擬「測得第二暫存器」後第一暫存器的均勻週期疊加：
    x0 = np.random.randint(0, r_of(N, a))  # 相位隨機
    r = r_of(N, a)
    amps = np.zeros(N_state, dtype=complex)
    k = 0
    while x0 + k*r < N_state:
        amps[x0 + k*r] = 1/np.sqrt(N_state // r + 1)
        k += 1
    # 步驟 3：QFT
    fourier = np.fft.fft(amps, norm='ortho')
    probs = abs(fourier)**2
    measured = np.random.choice(N_state, p=probs/probs.sum())
    # 步驟 4：連分數反推 r
    frac = Fraction(measured, N_state).limit_denominator(N)
    return frac.denominator

def r_of(N, a):
    r, val = 1, a % N
    while val != 1:
        val = val * a % N
        r += 1
    return r

def factor(N):
    for _ in range(100):
        a = np.random.randint(2, N)
        if gcd(a, N) != 1:
            return gcd(a, N)
        r = shor_simulate(N, a, n_qubits=10)
        if r % 2 == 0:
            f1, f2 = gcd(a**(r//2) - 1, N), gcd(a**(r//2) + 1, N)
            if 1 < f1 < N:
                return f1
    return None

print("factor(15) =", factor(15))    # 3 或 5
print("factor(21) =", factor(21))    # 3 或 7

（真實 Shor 用量子 QFT；此處以 numpy FFT 模擬量子測量的統計行為，邏輯完全相同。）

結案 -- 後果與影響#

• RSA 密碼學的危機成真：RSA、Diffie–Hellman、橢圓曲線密碼（ECC）在理論上全部被 Shor 演算法破解，催生了「後量子密碼學」（NIST 於 2024 年標準化 ML-KEM 等抗量子演算法）。
• 量子糾錯的誕生：分解實用級 RSA 金鑰需要數百萬個邏輯閘，但真實量子位元有雜訊。Shor 的成果使「容錯」成為必須——1995 年 Shor 本人提出第一個量子糾錯碼（9-qubit code），隨後 Steane 碼、CSS 碼、表面碼（surface code）接續發展，「可容錯量子計算」定理（ threshold theorem）確立。
• 量子計算從學術好奇變成國家戰略：各國政府與科技公司（IBM、Google、微軟）投入量子硬體研發。
• BQP（量子多項式時間）正式成為與 P/NP 並列的複雜度類別；因式分解問題落入 \(\text{BQP} \setminus \text{(已知 BPP)}\) 。
• 1996 年 Grover 演算法接棒，量子演算法版圖成形。

關鍵人物與文獻#

• Peter Shor（1959– ），美國，AT&T Bell Labs / MIT。
• Shor, P., "Algorithms for Quantum Computation: Discrete Logarithms and Factoring", FOCS (1994)。
• Shor, P., "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer", SIAM J. Comput. 26, 1484 (1997)。
• Shor, P., "Scheme for Reducing Decoherence in Quantum Computer Memory", Phys. Rev. A 52, R2493 (1995)（第一個量子糾錯碼）。
• Simon, D., "On the Power of Quantum Computation", FOCS (1994)。
• Rivest, Shamir, Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", CACM 21, 120 (1978)。
• Nielsen & Chuang, Quantum Computation and Quantum Information (2000)。