8.1 從分解到週期尋找#

概念說明#

Shor 演算法的第一段是純古典的數論約化：把「分解 \(N\) 」變成「找某函式的週期」。

約化步驟（ \(N\) 為奇合成數、非質數次方）：

1. 隨機選 \(a \in \{2, \dots, N-1\}\) ；若 \(\gcd(a, N) > 1\) ，直接得到一個因數（運氣好，機率不小）。
2. 考慮函式 \(f(x) = a^x \bmod N\) 。由歐拉定理， \(f\) 是週期函式：存在最小正整數 \(r\) （階，order）使 \(a^r \equiv 1 \pmod N\) 。
3. 若 \(r\) 為偶數且 \(a^{r/2} \not\equiv -1 \pmod N\) ，則

即 \(N \mid (a^{r/2}-1)(a^{r/2}+1)\) ，但兩個因子都不是 \(N\) 的倍數，因此 \(\gcd(a^{r/2}-1, N)\) 與 \(\gcd(a^{r/2}+1, N)\) 是 \(N\) 的非平凡因數。

機率分析： \(a\) 是均勻隨機選的，可以證明「 \(r\) 偶且 \(a^{r/2}\not\equiv -1\) 」的機率 \(\ge 1/2\) ；失敗就換一個 \(a\) 重來，期望嘗試次數 \(\le 2\) 。

例： \(N = 21\) ，選 \(a=2\) ： \(2,4,8,16,11,1,\dots\) 週期 \(r=6\) ； \(2^3=8\) ， \(\gcd(7,21)=7\) 、 \(\gcd(9,21)=3\) ，得 \(21 = 3 \times 7\) 。✓

量子計算要解的就是第 2 步——找週期 \(r\) 。古典找 \(r\) 需要逐一計算 \(a^x \bmod N\) 直到回到 1， \(r\) 可大到 \(\varphi(N) \approx N\) ，是指數（在位元數 \(\log N\) 上）時間；量子 QFT 把它壓成多項式。

Python 範例#

import math, random

def classical_factor_via_period(N, a):
    """已知 a，古典（慢）法找週期並分解"""
    r, x = 1, a % N
    while x != 1:
        x = (x * a) % N
        r += 1
    if r % 2 != 0:
        return None
    p = pow(a, r//2, N)
    if p == N - 1:
        return None
    return math.gcd(p - 1, N), math.gcd(p + 1, N)

def shor_classical_loop(N, quantum_period_fn, tries=10, seed=0):
    """完整外層：隨機 a -> 量子找 r -> gcd 分解"""
    rng = random.Random(seed)
    for t in range(tries):
        a = rng.randrange(2, N)
        g = math.gcd(a, N)
        if g > 1:
            return g, N // g, f"第 {t+1} 次抽到 a={a}，gcd 直接命中"
        r = quantum_period_fn(a, N)
        if r % 2 == 0 and pow(a, r//2, N) != N - 1:
            f1 = math.gcd(pow(a, r//2) - 1, N)
            return f1, N // f1, f"a={a}, r={r}"
    return None

# 用古典週期當量子部分的替身，先驗證數論邏輯
def slow_period(a, N):
    r, x = 1, a % N
    while x != 1:
        x = x * a % N
        r += 1
    return r

for N in [15, 21, 35, 91]:
    print(N, "->", shor_classical_loop(N, lambda a, N: slow_period(a, N), seed=3))

複雜度分析#

• 古典找週期： \(O(r)\) 次模乘法， \(r\) 可達 \(O(N) = O(2^{\log N})\) ——位元數上是指數。
• 量子週期尋找（8.2 節）： \(O(\log N)\) 次 \(U_a\) （模冪）+ QFT 的 \(O((\log N)^2)\) 閘。
• Shor 整體： \(O((\log N)^2(\log\log N)(\log\log\log N))\) 次閘級運算，慣稱 \(O((\log N)^3)\) 。
• 對照：數域篩法 \(e^{O((\log N)^{1/3}\cdot)}\) ；2048 位元 RSA 的分解，古典估計需數十億年，容錯量子電腦估計約 8 小時（約 2000 萬個物理量子位元，Gidney–Ekerå 2019）。

練習#

1. 對 \(N=35\) 、 \(a=3\) ，手算 \(a^x \bmod 35\) 的序列、求 \(r\) ，並完成分解。
2. 證明「 \(r\) 奇或 \(a^{r/2}\equiv-1\) 」發生的機率 \(\le 1/2\) （可查閱 Shor 原文的機率論證）。
3. （程式）驗證：對 \(N=15\) 的所有 \(a \in \{2,\dots,14\}\) ，分類哪些 \(a\) 能成功分解，統計成功率是否 \(\ge 1/2\) 。