Shor 1994 — 量子傅里叶变换把分解整数变成找周期

待复核

是什么

Shor 算法是一套用量子计算机在多项式时间内分解整数、求离散对数的方法。日常类比：像听一首歌里隐藏的鼓点周期，普通耳朵要一拍一拍数，量子傅里叶变换像调音台，能把周期对应的频率直接放大出来。

这篇论文的核心不是“量子计算机更快”这一句空话，而是给出具体路线：先把问题改写成“找某个函数重复出现的周期”，再用量子叠加同时试很多输入，用量子傅里叶变换让正确周期在测量时更容易露出来。

它直接击中了 RSA 和 Diffie-Hellman 一类公钥密码的假设：经典计算机上很难分解大整数、很难求离散对数；如果大型稳定量子计算机存在，这两个难题就不再是可靠地基。

为什么重要

不理解 Shor 1994，下面这些事都没法解释：

为什么“量子计算会威胁 RSA”不是科幻口号，而是来自一条清楚的算法链路
为什么量子傅里叶变换不是普通 FFT 的直接加速版，而是用干涉把周期信息转成测量概率
为什么分解整数本身被转成“求阶”问题，最后还要靠经典的 gcd 和连分数收尾
为什么论文一边给出多项式算法，一边反复提醒真实量子计算机还要面对退相干和门精度

核心要点

先把分解变成找周期。类比：打不开锁时，不直接砸锁，而是找齿轮转几下会回到原位。给定随机的 $x$，找最小 $r$ 使 $x^r \equiv 1 \pmod n$；如果 $r$ 合适，就能用 gcd 拆出因子。
量子部分负责找周期，经典部分负责读结果。类比：相机拍到模糊条纹后，还要用尺子量间距。量子计算产生一个接近 $d/r$ 的比例 $c/q$，经典连分数把这个比例还原成候选的 $r$。
傅里叶变换是“让周期变亮”的步骤。类比：白噪声里有固定节拍，频谱图会在对应频率冒尖。论文证明量子傅里叶变换可以用多项式数量的量子门实现，所以整个方案不是指数级地偷藏在子程序里。

实践案例

案例 1：为什么“求阶”能帮忙分解 15

from math import gcd

n = 15
x = 2
r = 4  # 2^4 = 16 = 1 (mod 15)
print(gcd(x ** (r // 2) - 1, n))
print(gcd(x ** (r // 2) + 1, n))

逐部分解释：

r = 4 是 2 在模 15 乘法里的周期，也叫“阶”
2^(r/2) 等于 4，4 - 1 和 4 + 1 刚好分别带着 3、5 的信息
gcd 是经典算法，量子计算机真正帮忙的是更快找到这个 r

案例 2：测量值怎样变回周期

from fractions import Fraction

c = 64  # 靠近 1/4 * 256，模拟测到周期峰
q = 256
guess = Fraction(c, q).limit_denominator(15)
print(guess)  # 1/4，分母 4 即候选周期

逐部分解释：

量子测量给出的不是“周期 r”，而是一个整数 c（理想峰在 k·q/r 附近）
c / q 往往靠近某个 d / r，这里用连分数找小分母近似
分母只是候选值，真实算法还要检查 x^r ≡ 1 (mod n) 是否成立

案例 3：离散对数的目标长什么样

p = 17
g = 3
x = 13
for r in range(p - 1):
    if pow(g, r, p) == x:
        print(r)
        break

逐部分解释：

离散对数问的是：g 乘自己多少次，才会在模 p 下变成 x
经典暴力枚举会随 p 变大而不可用，真实算法不会这样硬试
Shor 的离散对数算法用两个指数寄存器和两次量子傅里叶变换，把隐藏的 r 从测量关系里解出来

踩过的坑

把 Shor 算法理解成“量子电脑同时试完所有因子”：真正被放大的是周期结构，不是每个候选因子的答案标签。
以为量子傅里叶变换就是经典 FFT 更快版：QFT 操作的是量子态振幅，输出通常不能完整读出，只能通过测量拿到被干涉放大的信息。
忘记可逆计算的成本：量子门必须整体可逆，所以模指数运算要小心清理工作空间，否则垃圾信息会破坏干涉。
把多项式算法等同于马上破解 RSA：论文证明的是复杂度可能性，现实还需要足够多、足够稳定、错误率足够低的量子比特。

适用 vs 不适用场景

适用：

分解大整数，尤其是理解 RSA 为什么依赖经典计算困难性
求有限域或某些阿贝尔群上的离散对数，理解 Diffie-Hellman 风险
学习“隐藏周期问题”这一类量子算法套路
理解量子算法里“量子采样 + 经典后处理”的分工

不适用：

直接解决所有 NP-complete 问题，论文没有证明量子计算能做到这件事
在普通电脑上加速任意程序，算法依赖量子叠加、干涉和测量
替代密码工程里的所有分析，实际系统还涉及参数、协议和迁移成本
忽略物理实现问题，退相干、门误差和纠错仍是落地门槛

历史小故事（可跳过）

1982 年：Feynman 提出用量子系统模拟量子系统，打开“计算模型可以换物理底座”的想象。
1985 年：Deutsch 描述通用量子计算机，说明量子计算可以被当成一种通用计算模型研究。
1994 年：Shor 在 FOCS 提出分解整数和离散对数的多项式时间量子算法，公钥密码的长期假设第一次被明确撼动。
1994-1995 年：Coppersmith 给出更实用的近似量子傅里叶变换构造，Shor 后续文稿也吸收这类门数优化。
1995 年以后：退相干、量子纠错和可实现门集成为主战场，因为算法已经说明“如果机器能造出来，会发生什么”。

学到什么

分解整数的关键不是直接找因子，而是找阶：一旦阶满足偶数且非平凡条件，gcd 就能拆出因子。
QFT 的价值是把周期变成概率峰：它不让你读出完整频谱，而是提高测到有用 c 的概率。
量子算法常常不是全量替代经典算法：Shor 仍然依赖模指数、连分数、gcd 和概率放大这些经典工具。
密码学安全依赖计算模型：同一个数学难题，在经典模型和量子模型下的难度可能完全不同。

关联

rsa —— RSA 的安全性依赖大整数分解困难，Shor 算法正面击中这个假设
diffie-hellman-1976 —— Diffie-Hellman 依赖离散对数困难，论文第二个算法直接覆盖这类问题
turing-1936 —— Turing 给出经典可计算模型，Shor 展示换成量子模型后复杂度边界会变化
cook-levin —— NP-complete 是另一类困难性，论文明确没有证明量子计算能高效解决它
quantum-supremacy-2019 —— 后来的实验路线尝试证明量子设备在特定任务上超过经典模拟
cryptoverif-2008 —— 形式化密码验证关心协议逻辑，Shor 提醒底层困难假设也会被计算模型改变

反向链接

feynman-simulating-physics-1982 —— Feynman 1982 — 量子计算从模拟物理开始
quantum-supremacy-2019 —— Quantum Supremacy 2019 — 量子机用 200 秒做完超算 1 万年的事

Shor 1994 — 量子傅里叶变换把分解整数变成找周期

是什么

为什么重要

核心要点

实践案例

案例 1：为什么“求阶”能帮忙分解 15

案例 2：测量值怎样变回周期

案例 3：离散对数的目标长什么样

踩过的坑

适用 vs 不适用场景

历史小故事（可跳过）

学到什么

延伸阅读

关联

反向链接