量子傅里叶与 Shor · 破 RSA 的直觉 · 写给程序员的量子计算

Shor 算法能在多项式时间内分解大整数，从而击穿 RSA——这是全世界准备「后量子密码」的原因。这一章讲清它的引擎量子傅里叶变换(QFT)、「分解 → 找周期」的巧妙归约，给出 QFT 代码骨架，并说清它离威胁你还有多远。

量子傅里叶与 Shor · 破 RSA 的直觉

量子算法里名气最大的，非 Shor 算法莫属——它能在多项式时间内分解大整数。这件事的分量在于：当今互联网的安全基石 RSA，正建立在「分解大整数很难」之上。 Shor 一旦跑在足够大的量子计算机上，RSA 就被击穿了。这一章讲清它凭什么能做到，以及它离你还有多远。

Shor 的完整实现相当复杂，不是一章能写全的。但它的核心思想清晰得出人意料，我们抓住主干。

巧妙的归约：分解 → 找周期

第一步是个纯经典的数学技巧：把「分解 $N$ 」转化成「求一个函数的周期」。

任取一个和 $N$ 互质的数 $a$ ，考察这个函数：

f(x) = a^x \bmod N

它是周期性的——存在一个周期 $r$ ，使得 $a^{x+r} \equiv a^x \pmod N$ 。而数论保证：只要求出这个周期 $r$ （且 $r$ 是偶数），就能用 $\gcd(a^{r/2}\pm 1,\, N)$ 算出 $N$ 的因子。

所以整个难题被压缩成了一件事：求 $f(x)=a^x\bmod N$ 的周期 $r$ 。 这一步归约是经典的（不需要量子）。经典难在哪？周期 $r$ 可能极大，一个个试要指数时间。而「找周期」，恰恰是量子计算最擅长的——因为周期性就是「频率」，而提取频率有个神器：傅里叶变换。 Shor 的量子部分，就是用量子傅里叶变换高效地找出这个周期。

引擎：量子傅里叶变换(QFT)

经典的离散傅里叶变换(DFT)能从一串信号里提取「频率成分」；量子傅里叶变换(QFT) 是它的量子版，把一个态变换成：

\text{QFT}\,\ket{x} = \frac{1}{\sqrt{N}}\sum_{y=0}^{N-1} e^{2\pi i\, xy/N}\,\ket{y}

它的威力在于：如果你把 $f$ 的周期性「装进」一个叠加态（通过预言机算 $a^x\bmod N$ ），再对它做 QFT，那么周期性会变成振幅上的「尖峰」——测量时大概率落在 $r$ 的倍数相关的位置上，几次测量 + 一点经典后处理，就能反推出周期 $r$ 。这个「用 QFT 从叠加里读出周期」的过程，正式名字叫相位估计(phase estimation)，是 Shor 的心脏。

QFT 在 Qiskit 里是现成的，可以直接看它的线路：

from qiskit.circuit.library import QFT

qft = QFT(3)                      # 3-qubit 量子傅里叶变换
print(qft.decompose().draw())
# 你会看到一串 H 门 + 受控相位旋转门(CP)+ 末尾的 qubit 交换

QFT 为什么快？ 经典 FFT 处理 $2^n$ 个数要 $O(n\,2^n)$ 次操作；而 QFT 用 $O(n^2)$ 个门就把变换作用在了整个 $2^n$ 维叠加态上——指数级的优势。当然，老问题还在：你不能把变换后的 $2^n$ 个振幅全读出来（测量只给一个）。但对「找周期」这个特定任务，你不需要全部——你只要那个尖峰的位置，而 QFT 让尖峰大概率被你测到。这又是「用干涉把要的信息聚焦成可测结果」的老套路，只是玩得更高级。

完整 Shor 长什么样

把主干串起来，Shor 是「经典 + 量子」的混合：

图表加载中…

真正难写的是中间那步的量子部分——它需要一个能可逆计算 $a^x \bmod N$ 的大线路（模幂），外加相位估计和 QFT，qubit 数和门数都不少。所以本章给的是直觉与骨架，不是可跑的完整分解器（那要几百上千行 + 很多 qubit）。但你现在能看懂它的逻辑了：分解 → 找周期（经典归约）→ QFT 找周期（量子）→ 反推因子（经典）。

它离你有多远

别恐慌，但要行动。 分解一个 RSA-2048 的密钥，需要数千个逻辑 qubit——而逻辑 qubit 要靠纠错从成千上万个物理 qubit 里「提炼」出来，总共可能要数百万个高质量物理 qubit。今天最好的量子计算机才几百到上千个含噪物理 qubit，离这个规模还很远，普遍预计还要多年甚至十几年。

可为什么全世界（NIST 等）已经在紧锣密鼓推后量子密码(PQC)？因为有个「先存下来，以后再解密(harvest now, decrypt later)」的威胁：攻击者现在就截获并囤积你的加密流量，等未来量子计算机成熟了再回头解密。对需要长期保密的数据（国家机密、医疗档案），这意味着威胁其实已经开始。所以迁移到抗量子算法（基于格、哈希等，Shor 攻不动的数学难题）是当下正在发生的事——而 Grover 那章说过，对称加密加长密钥即可，真正要换的是 RSA/ECC 这类非对称算法。

小结与下一章

Shor 靠一个巧妙归约把「分解大整数」变成「求 $a^x\bmod N$ 的周期」，再用量子傅里叶变换 + 相位估计高效找周期，从而击穿 RSA。QFT 用 $O(n^2)$ 个门作用于指数大的叠加、把周期性聚焦成可测的尖峰，是它的引擎。但 Shor 要数百万物理 qubit，离实用尚远——不过「先囤积后解密」的威胁，已经在推动全球迁移后量子密码。

算法四章（预言机、DJ、Grover、Shor）展示了量子计算的理论威力。可现实里的量子计算机为什么这么难造、跑起来错误一堆？最后一站直面现实。👉 噪声、退相干与 NISQ：真机为什么这么难。

参考文献

[1] Shor.「Algorithms for quantum computation: discrete logarithms and factoring.」1994. —— 原始论文。
[2] Qiskit 官方文档.「Quantum Fourier Transform / Shor's algorithm.」https://learning.quantum.ibm.com —— QFT 与 Shor 实现。
[3] NIST.「Post-Quantum Cryptography.」https://csrc.nist.gov/projects/post-quantum-cryptography —— 后量子密码标准化。

量子傅里叶与 Shor · 破 RSA 的直觉