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

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

- 作者：David（道雾轩）
- 专栏：写给程序员的量子计算（https://daiw.org/manual/quantum-computing.md）
- 最后更新：2026-07-14
- 原文：https://daiw.org/manual/quantum-computing/qft-shor
- 转载与引用：请注明出处并附原文链接（https://daiw.org/about/copyright）

# 量子傅里叶与 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$ 的因子**。

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

## 引擎：量子傅里叶变换(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$ 的周期性「装进」一个叠加态（通过[预言机](https://daiw.org/manual/quantum-computing/oracle)算 $a^x\bmod N$），再对它做 QFT，那么**周期性会变成振幅上的「尖峰」**——测量时大概率落在 $r$ 的倍数相关的位置上，几次测量 + 一点经典后处理，就能反推出周期 $r$。这个「用 QFT 从叠加里读出周期」的过程，正式名字叫**相位估计(phase estimation)**，是 Shor 的心脏。

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

```python
from qiskit.circuit.library import QFT

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

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

## 完整 Shor 长什么样

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

```mermaid
flowchart TB
  A["经典:随机选 a,算 gcd(a,N)<br/>(碰巧不互质就直接得因子)"] --> B["量子:用相位估计 + QFT<br/>求 f(x)=a^x mod N 的周期 r"]
  B --> C["经典:由 r 算 gcd(a^(r/2)±1, N)<br/>得到 N 的因子"]
  C --> D{"成功?"}
  D -->|"否(r 是奇数等)"| A
  D -->|"是"| E["分解完成"]
```

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

## 它离你有多远

<Callout type="warn">
  **别恐慌，但要行动。** 分解一个 RSA-2048 的密钥，需要**数千个逻辑 qubit**——而逻辑 qubit 要靠[纠错](https://daiw.org/manual/quantum-computing/noise-nisq)从**成千上万个物理 qubit** 里「提炼」出来，总共可能要**数百万个高质量物理 qubit**。今天最好的量子计算机才**几百到上千个**含噪物理 qubit，离这个规模还很远，普遍预计还要**多年甚至十几年**。

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

## 小结与下一章

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

算法四章（预言机、DJ、Grover、Shor）展示了量子计算的理论威力。可现实里的量子计算机为什么这么难造、跑起来错误一堆？最后一站直面现实。👉 [噪声、退相干与 NISQ：真机为什么这么难](https://daiw.org/manual/quantum-computing/noise-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 —— 后量子密码标准化。