Shor 算法：从周期查找到整数分解
一句话定义
Shor 算法把大整数分解归约为求模幂函数 ax mod N 的周期 r，用量子傅里叶变换在多项式时间完成周期查找，从而威胁 RSA 等基于分解/离散对数的公钥体系。
为什么重要
1994 年 Shor 的这项工作是量子计算从冷门物理话题变成国家级战略议题的转折点——它第一次展示了"量子加速 + 现实后果"的组合。理解它需要三块拼图：数论归约（分解→周期）、量子周期查找（QFT，kp-016）、以及诚实的资源估算（为什么今天还破不了任何密码）。本节是全库篇幅最大的单知识点，因为它同时是数学课与风险教育课。
前置知识
kp-016（QFT 与谱峰定位）。数论部分自带：模运算、最大公约数 gcd、欧拉函数的思想，均在使用处给出。
核心概念
- 归约核心：随机选 a（与 N 互素），若能找到 ax mod N 的周期 r（即 ar ≡ 1 (mod N)），则 gcd(ar/2−1, N) 与 gcd(ar/2+1, N) 大概率给出 N 的非平凡因子。
- 奇偶与互素检查：r 为奇数或 ar/2 ≡ −1 (mod N) 时该次失败，换 a 重来；单次成功率下界约 1/(2 log N) 量级，重复多项式次即可。
- 量子部分：构造等幅叠加 Σx|x⟩，用可逆电路计算 ax mod N 并回踢（kp-015 技巧），得 1√NΣx|x⟩|ax mod N⟩；对第一寄存器做 QFT，谱峰位于 kN/r。
- 后处理：测得峰位 c ≈ kN/r，用连分数展开逼近 c/N 得 k/r，取最小算术分母即 r。
- 资源现实：分解 RSA-2048 的容错级估算需要约 2000 万物理比特（数百万逻辑比特）与数小时——今天最大的机器相去 4–5 个数量级。
直观类比
分解 15 找周期像"测一台奇怪钟表的循环长度"：从 2 开始不断乘 2（逢 15 取余），序列 2,4,8,1,2,4,8,1…每 4 步回原点，r=4。量子计算机的做法是同时启动"所有步数的钟"，用 QFT 听出这些钟的共同节拍——一次测量抓到一个节拍样本，连分数还原出周期。这也是"量子模拟量子"之外的另一课：量子计算最擅长的是隐含周期结构的代数问题。
原理与机制
分四步（每步都可复核）。
其一，数论归约：N 为奇合数且非素数幂时，取随机 1 < a < N，gcd(a,N)=1（否则直接得因子）。由欧拉定理 aφ(N) ≡ 1，故模幂序列周期存在。设 r 为最小周期且为偶，记 y = ar/2，则 y² ≡ 1 (mod N)，即 (y−1)(y+1) ≡ 0 (mod N)；若 y ≢ ±1，则 N 整除 (y−1)(y+1) 但不整除任一因子，故 gcd(y−1,N) 与 gcd(y+1,N) 都是非平凡因子。例：N=15，a=2，r=4，y=4，gcd(3,15)=3，gcd(5,15)=5。
其二，量子周期查找：两寄存器叠加 |x⟩|0⟩ → 模幂门 → 1√NΣ|x⟩|aˣ mod N⟩；测量第二寄存器（或保持不动，效果相同），第一寄存器坍缩为周期 r 的等幅叠加——周期信息只存在于振幅的"节拍"中，直接测不到。
其三，QFT 读出：对第一寄存器做 QFT，幅值集中于 |round(kN/r)⟩；一次测量得到一个 c ≈ kN/r。
其四，经典后处理：连分数展开 c/N，找分母 < N 的最优逼近得 k/r；约分取 r′，验证 ar′ ≡ 1 即 r。失败（r 奇、y≡−1、逼近失败）则换 a 重来。总复杂度：QFT O(n²) + 模幂电路 O(n³)（n=log N），多项式级；对比经典已知最优（数域筛）为次指数级 exp((64/9)1/3(ln N)1/3(ln ln N)2/3)。
公式或模型
归约恒等式：ar ≡ 1 (mod N) ⟹ N | (ar/2−1)(ar/2+1)。
谱峰：P(c) ∝ |Σj e2πijc·r/N|² 在 c ≈ kN/r 处极大（kp-016 结论的直接应用）。
容错资源（Gidney–Ekerå 2021）：RSA-2048 ≈ 20×10⁶ 物理比特 / 8 小时（错误率 10⁻³ 假设）；当前最大处理器约 10³ 物理比特——差距约 4 个数量级。
图示
实例或案例
历史上著名的"IBM 2001 分解 15"演示用的是预编译的简化电路（周期已知，常数级线路），它证明了控制技术而非性能；2012 年光子平台的 21=3×7 同类演示同理。资源侧的正经参照是 Gidney–Ekerå (2021) 的容错估算——本节"常见误区"一栏的正主。教学上建议在 kp-030 平台用模拟器跑 N=15、21 的完整 Shor 电路（约 12–18 比特可承受），亲眼看到连分数后处理把杂乱采样还原成 r。
与其他知识点的关系
kp-016 提供发动机；kp-015 的相位回踢在模幂门处再次出场；kp-029 讨论其密码学后果与对策；kp-033 把"Shor 能跑通"与"NISQ 跑不动 Shor"区分开。
常见误区
- "量子计算机已经能破解银行加密"：不能。分解 RSA-2048 需要百万级逻辑比特，当前机器约 10²–10³ 物理比特，差距 4–5 个数量级；且错误率需低于容错阈值（kp-026）。
- "Shor 威胁一切加密"：只威胁基于分解与离散对数的公钥体系；对称密码（AES）面对 Grover 型攻击只需把密钥加倍（kp-029、kp-033）。
- "15=3×5 的演示说明 Shor 已实用"：演示级电路常数化处理了周期查找，不含 Shor 的真实复杂度——阅读此类新闻时先问电路规模。
自测题
- 用 a=7 分解 N=15，写出 r 与两个 gcd。
- 为什么必须在量子部分之后用连分数后处理？
- 单次失败后为什么"重来"是可行策略？
答案要点：7²=49≡4、7⁴≡16≡1，r=4；gcd(6,15)=3、gcd(8,15)=1——取 3，另一因子 5。
答案要点：测量得到的是 kN/r 的近似整峰位 c，k 未知；连分数用 c/N 的最优有理逼近恢复 k/r，从而得 r。
答案要点：每次选新 a 独立，单次成功率有下界（约 1/(2 log N) 量级），期望重复次数为多项式。
延伸阅读
P. W. Shor (1997) SIAM J. Comput. 原始论文；C. Gidney、M. Ekerå (2021) Quantum 5, 433（资源估算的现实参照）。