# Shor 算法详解：从经典因数分解到量子霸权

Shor 算法（Shor's Algorithm）由 Peter Shor 于 1994 年提出，是量子计算领域最具里程碑意义的算法之一。它证明了量子计算机能够在多项式时间内完成整数因数分解——而这个问题对经典计算机而言，在大数情况下仍是计算瓶颈，也正是 RSA 加密体系安全性的根基。

## 问题背景：为什么因数分解很重要

RSA 加密的核心假设是：给定两个大素数 $p, q$，计算 $N = p \times q$ 很容易，但从 $N$ 反推出 $p, q$ 极其困难。目前最好的经典算法（数域筛法，Number Field Sieve）的时间复杂度约为：

$$O\!\left(\exp\!\left(\left(\frac{64}{9}\right)^{1/3} (\log N)^{1/3} (\log \log N)^{2/3}\right)\right)$$

这是亚指数级的：它远慢于任何多项式，又远快于指数级的暴力搜索。即便如此，对于 2048 位的 RSA 模数，经典计算机仍需要天文数字般的运算量。

而 Shor 算法的时间复杂度为 $O((\log N)^3)$——多项式级，理论上可在数小时内分解 2048 位整数。

## Shor 算法的核心思想

Shor 算法将因数分解问题归约为求阶问题（order-finding problem）：给定整数 $N$（待分解）和随机选取的 $a$（$1 < a < N$，且 $\gcd(a, N) = 1$），求最小正整数 $r$ 使得 $a^r \equiv 1 \pmod{N}$。这个 $r$ 称为 $a$ 模 $N$ 的阶（multiplicative order）。

一旦求得 $r$：若 $r$ 为偶数且 $a^{r/2} \not\equiv -1 \pmod{N}$，则 $\gcd(a^{r/2} - 1,\; N)$ 与 $\gcd(a^{r/2} + 1,\; N)$ 立即给出 $N$ 的非平凡因子（引理 1 及其证明见下文）；对随机选取的 $a$，这两个条件以至少 $1/2$ 的概率同时满足（证明见下文"失败概率分析"）。

量子部分的任务就是高效求阶，其结构是"相位估计 + 连分数"：量子傅里叶变换把周期 $r$ 转化为测量值 $j$，使得 $j/2^n$ 是某个分母为 $r$ 的分数 $c/r$ 的近似；再用经典的连分数（continued fraction）展开从这一近似中恢复出 $r$。

## 算法步骤

### 第一步：经典预处理

1. 随机选取 $a \in \{2, 3, \ldots, N-1\}$
2. 计算 $\gcd(a, N)$，若大于 1 则直接得到因子，算法结束

### 第二步：量子求阶（核心）

这是量子计算机发挥作用的步骤。构造两个量子寄存器：

- **寄存器 1**：$n = \lceil \log_2 N^2 \rceil$ 个量子比特，用于存储 $x$ 的叠加态；以下记 $Q = 2^n$，注意 $Q \geq N^2$
- **寄存器 2**：$\lceil \log_2 N \rceil$ 个量子比特，用于存储 $a^x \bmod N$ 的结果

**操作流程：**

1. 初始化寄存器 1 为等权叠加态：$|\psi\rangle = \frac{1}{\sqrt{Q}} \sum_{x=0}^{Q-1} |x\rangle$

2. 计算模幂运算 $|x\rangle|0\rangle \to |x\rangle|a^x \bmod N\rangle$（可用模幂电路高效实现）

3. 对寄存器 2 进行测量，得到某个值 $y = a^{x_0} \bmod N$，寄存器 1 坍缩为所有满足 $a^x \equiv y \pmod{N}$ 的 $x$ 的等权叠加，即 $x = x_0,\; x_0 + r,\; x_0 + 2r,\; \ldots$

4. 对寄存器 1 施加量子傅里叶变换（Quantum Fourier Transform, QFT）：$\text{QFT}: |j\rangle \mapsto \frac{1}{\sqrt{Q}} \sum_{k=0}^{Q-1} e^{2\pi i jk / Q} |k\rangle$

5. 测量寄存器 1，以高概率得到接近 $Q / r$ 的整数倍的值 $j$

6. 用连分数展开从测量结果 $j/Q$ 中提取候选分母，并逐一验证 $a^{q} \bmod N$ 是否等于 1，取通过验证的最小候选作为 $r$；若所有候选都失败，重跑本步骤

### 第三步：经典后处理

1. 若 $r$ 为奇数，回到第一步重新选 $a$
2. 计算 $a^{r/2} \bmod N$，若 $\equiv -1 \pmod{N}$，回到第一步
3. 计算 $\gcd(a^{r/2} - 1,\; N)$ 和 $\gcd(a^{r/2} + 1,\; N)$，得到非平凡因子

## 理论推导

以下给出算法正确性的完整数学证明。

### 从周期到因子：为什么求阶能分解 N

**引理 1**：设 $N$ 为奇合数，$\gcd(a, N) = 1$，$r$ 为 $a$ 模 $N$ 的阶。若 $r$ 为偶数且 $a^{r/2} \not\equiv -1 \pmod{N}$，则 $\gcd(a^{r/2} - 1,\; N)$ 和 $\gcd(a^{r/2} + 1,\; N)$ 都是 $N$ 的非平凡因子（即严格介于 $1$ 与 $N$ 之间）。

**证明**分四步。

第一步：$N$ 整除两个因子的乘积。由阶的定义 $a^r \equiv 1 \pmod{N}$，即 $N \mid (a^r - 1)$。$r$ 为偶数，故 $r/2$ 是正整数，可对 $a^r - 1 = (a^{r/2})^2 - 1$ 用平方差公式：

$$a^r - 1 = (a^{r/2} - 1)(a^{r/2} + 1)$$

因此 $N \mid (a^{r/2} - 1)(a^{r/2} + 1)$。

第二步：两个因子几乎互素。它们的差为 2，而两个整数的公因数必整除其差，故

$$\gcd(a^{r/2} - 1,\; a^{r/2} + 1) \mid 2$$

若 $N$ 为偶数则可直接被 2 整除，无需 Shor 算法，故我们只需考虑奇数 $N$：$N$ 的每个素因子 $p$ 都是奇数，不整除 2，因此 $p$ 不能同时整除 $(a^{r/2} - 1)$ 和 $(a^{r/2} + 1)$。

第三步：素因子被划分到两侧。考虑 $N$ 的任一素幂因子 $p^e$（$p$ 奇素数）。由第一步 $p^e \mid (a^{r/2} - 1)(a^{r/2} + 1)$；由第二步 $p$ 只整除其中一个因子，于是 $p^e$ 的全部幂次只能落在同一个因子里。把 $N$ 的所有素幂按此划分，记

$$N_- = \gcd(a^{r/2} - 1, N), \qquad N_+ = \gcd(a^{r/2} + 1, N)$$

则 $N = N_- \cdot N_+$ 且 $\gcd(N_-, N_+) = 1$。

第四步：两个因子都是非平凡的。$N_- = N$ 当且仅当 $N \mid a^{r/2} - 1$，即 $a^{r/2} \equiv 1 \pmod{N}$。这不可能发生：$r$ 是使 $a^k \equiv 1 \pmod N$ 成立的最小正整数，而 $0 < r/2 < r$，若 $a^{r/2} \equiv 1$ 则与 $r$ 的最小性矛盾。$N_+ = N$ 当且仅当 $a^{r/2} \equiv -1 \pmod{N}$，已被引理的条件排除。于是 $N_-, N_+ < N$；又由 $N_- N_+ = N$ 知两者都不能是 1（若 $N_- = 1$ 则 $N_+ = N$，矛盾；$N_+$ 同理）。故两者都是 $N$ 的非平凡因子。∎

**具体验证**（以 $N = 15,\; a = 7,\; r = 4$ 为例）：

- $7^2 - 1 = 48$，$\gcd(48, 15) = 3$ ✓
- $7^2 + 1 = 50$，$\gcd(50, 15) = 5$ ✓
- $15$ 的素因子 $\{3, 5\}$ 被分别"捕获"

**失败概率分析**。算法失败有两种情况：$r$ 为奇数，或 $a^{r/2} \equiv -1 \pmod{N}$。我们以 $N = pq$（两个不同奇素数）为例把两种情况的概率都算出来；更一般的奇合数可用同样的计数方法处理。

预备计数：记 $v_2(m)$ 为整数 $m$ 所含素因子 2 的个数（即 $m = 2^{v_2(m)} \times$ 奇数）。设 $p - 1 = 2^{t_p} u_p$（$u_p$ 为奇数）。$\mathbb{Z}_p^*$ 是 $p - 1$ 阶循环群，其中阶整除 $2^s u_p$ 的元素恰有 $2^s u_p$ 个。因此，$a$ 模 $p$ 的阶 $r_p$ 满足 $v_2(r_p) = s$（$1 \le s \le t_p$）的比例为 $\frac{2^s u_p - 2^{s-1} u_p}{2^{t_p} u_p} = 2^{s-1-t_p}$，$v_2(r_p) = 0$（阶为奇数）的比例为 $2^{-t_p}$。由中国剩余定理（Chinese Remainder Theorem, CRT），$a$ 模 $N$ 均匀当且仅当 $a \bmod p$ 与 $a \bmod q$ 独立均匀；且 $a^k \equiv 1 \pmod N$ 当且仅当模 $p$、模 $q$ 同时为 1，故 $r = \operatorname{lcm}(r_p, r_q)$，其中 $r_p, r_q$ 是 $a$ 模 $p, q$ 的阶。

情况一（$r$ 为奇数）：$r = \operatorname{lcm}(r_p, r_q)$ 为奇数当且仅当 $r_p, r_q$ 都是奇数，概率为

$$2^{-t_p} \cdot 2^{-t_q} = 2^{-(t_p + t_q)} \le \frac{1}{4}$$

情况二（$a^{r/2} \equiv -1 \pmod N$）：设 $r$ 为偶数。$(a^{r/2})^2 \equiv 1 \pmod p$，而在域 $\mathbb{Z}_p$ 中 $1$ 的平方根只有 $\pm 1$，故 $a^{r/2} \bmod p \in \{+1, -1\}$，$\bmod q$ 同理。于是签号组合 $(a^{r/2} \bmod p,\; a^{r/2} \bmod q)$ 有四种可能：

- $(+,+)$：意味着 $a^{r/2} \equiv 1 \pmod N$，与 $r$ 的最小性矛盾，不可能发生（由 $v_2(r) = \max(v_2(r_p), v_2(r_q))$，至少一侧达到最大值，也可看出 $a^{r/2}$ 不可能模两个素数同时为 $+1$）；
- $(-,-)$：即 $a^{r/2} \equiv -1 \pmod{N}$，算法失败；
- $(+,-)$ 或 $(-,+)$：此时 $p$ 整除其中一个因子、$q$ 整除另一个，$\gcd(a^{r/2} \pm 1, N)$ 恰为 $\{p, q\}$，算法成功。

$(-,-)$ 何时发生？$a^{r/2} \equiv -1 \pmod p$ 等价于 $r_p \nmid r/2$，即 $v_2(r_p) = v_2(r)$（奇部自动相容，因为 $r_p \mid r$）；模 $q$ 同理。两侧同时为 $-1$ 等价于 $v_2(r_p) = v_2(r_q) = s$ 对某个 $s \ge 1$ 成立，其概率为

$$\sum_{s=1}^{m} 2^{s-1-t_p} \cdot 2^{s-1-t_q} = \frac{2^{2m} - 1}{3 \cdot 2^{t_p + t_q}}, \qquad m = \min(t_p, t_q)$$

（等比数列求和：公比为 4。）

把两种失败情况相加，总失败概率为

$$\frac{1}{2^{t_p+t_q}} + \frac{2^{2m}-1}{3 \cdot 2^{t_p+t_q}} = \frac{2^{2m} + 2}{3 \cdot 2^{t_p+t_q}} \le \frac{2^{2m} + 2}{3 \cdot 2^{2m}} \le \frac{1}{2}$$

其中用到 $t_p, t_q \ge m \ge 1$。等号在 $t_p = t_q = 1$（即 $p \equiv q \equiv 3 \pmod 4$）时取到，此时两种失败各占 $1/4$。结论：**单次随机选取 $a$ 的成功概率至少为 $1/2$，重复 $k$ 次后失败概率降至 $1/2^k$**。

以 $N = 15 = 3 \times 5$ 全量枚举验证（$\gcd(a,15)=1$ 的 $a$ 共 7 个）：

| $a$ | $r$ | $a^{r/2} \bmod 15$ | $(\bmod\ 3,\ \bmod\ 5)$ | 结果 |
|-----|-----|--------------------|--------------------------|------|
| 2 | 4 | 4 | $(+1, -1)$ | $\gcd(3,15)=3,\ \gcd(5,15)=5$ ✓ |
| 4 | 2 | 4 | $(+1, -1)$ | $3,\ 5$ ✓ |
| 7 | 4 | 4 | $(+1, -1)$ | $3,\ 5$ ✓ |
| 8 | 4 | 4 | $(+1, -1)$ | $3,\ 5$ ✓ |
| 11 | 2 | 11 | $(-1, +1)$ | $\gcd(10,15)=5,\ \gcd(12,15)=3$ ✓ |
| 13 | 4 | 4 | $(+1, -1)$ | $3,\ 5$ ✓ |
| 14 | 2 | 14 | $(-1, -1)$ | 失败（$a^{r/2} \equiv -1$）|

7 个中有 6 个成功，比例 $\approx 0.857 \ge 1/2$，与理论一致。

### QFT 提取周期的数学原理

测量寄存器 2 得到 $y$ 后，寄存器 1 坍缩为所有满足 $a^x \equiv y \pmod{N}$ 的 $|x\rangle$ 的等权叠加态。设最小的解为 $x_0 \in \{0, 1, \ldots, r-1\}$，则解集为 $\{x_0, x_0 + r, x_0 + 2r, \ldots\}$ 中不超过 $Q - 1$ 的那些，于是

$$|\phi\rangle = \frac{1}{\sqrt{M}} \sum_{k=0}^{M-1} |x_0 + kr\rangle, \qquad M = \left\lfloor \frac{Q - 1 - x_0}{r} \right\rfloor + 1 \approx \frac{Q}{r}$$

（项数 $M$ 的由来：要求 $x_0 + kr \le Q - 1$，即 $k \le (Q-1-x_0)/r$，故 $k$ 的最大值为 $\lfloor (Q-1-x_0)/r \rfloor$，共 $M$ 项。）

对 $|\phi\rangle$ 施加 QFT。第 $j$ 个分量的振幅为

$$\alpha_j = \frac{1}{\sqrt{Q \cdot M}} \sum_{k=0}^{M-1} e^{2\pi i j (x_0 + kr) / Q} = \frac{e^{2\pi i j x_0 / Q}}{\sqrt{Q M}} \sum_{k=0}^{M-1} \left[e^{2\pi i j r / Q}\right]^k$$

内层是公比为 $e^{2\pi i \Delta}$（$\Delta = jr / Q$）、共 $M$ 项的几何级数。用等比求和公式并提取公因子的相位，可得其模长为

$$\left|\sum_{k=0}^{M-1} e^{2\pi i k \Delta}\right| = \left|\frac{\sin(\pi M \Delta)}{\sin(\pi \Delta)}\right|$$

当 $\Delta$ 接近整数时各项几乎同相，级数模长接近 $M$，发生相长干涉；当 $\Delta$ 接近半整数时各项几乎两两反相，级数模长接近 0，发生相消干涉。定量地，利用不等式 $\sin t \ge \frac{2}{\pi} t$（$0 \le t \le \pi/2$）与 $|\sin t| \le |t|$：当 $|\Delta| \le \frac{1}{2M}$ 时，

$$\left|\frac{\sin(\pi M \Delta)}{\sin(\pi \Delta)}\right| \ge \frac{2 M |\Delta|}{\pi |\Delta|} = \frac{2M}{\pi}$$

即模长至少是最大值的 $2/\pi \approx 0.64$ 倍。

现在确定峰的位置。对每个 $c \in \{0, 1, \ldots, r-1\}$，取 $j_c$ 为最接近 $\frac{cQ}{r}$ 的整数，则 $\left|j_c - \frac{cQ}{r}\right| \le \frac{1}{2}$，于是

$$|\Delta| = \frac{r}{Q}\left|j_c - \frac{cQ}{r}\right| \le \frac{r}{2Q} \lesssim \frac{1}{2M}$$

（最后一步是因为 $M \approx Q/r$；由于 $Q \ge N^2 \gg r$，边界效应可忽略。）因此峰处的振幅满足 $|\alpha_{j_c}| \gtrsim \frac{2}{\pi}\sqrt{\frac{M}{Q}}$，测量概率

$$P(j_c) \gtrsim \frac{4}{\pi^2} \cdot \frac{M}{Q} \approx \frac{4}{\pi^2} \cdot \frac{1}{r}$$

$r$ 个峰合计的总概率约为 $4/\pi^2 \approx 0.40$，这就是单次量子运行"落在好峰上"的概率下限。

关键在于峰的位置编码了 $r$：由 $\left|j_c - \frac{cQ}{r}\right| \le \frac{1}{2}$ 两边除以 $Q$ 得

$$\left|\frac{j_c}{Q} - \frac{c}{r}\right| \le \frac{1}{2Q} \le \frac{1}{2N^2} < \frac{1}{2r^2}$$

（用到 $Q \ge N^2$ 与 $r < N$：$a$ 的阶整除群阶 $\varphi(N) < N$。）换言之，测量值 $j/Q$ 是某个以 $r$ 为分母的有理数 $c/r$ 的近似，且近似精度好到 $1/(2r^2)$ 以内。问题于是转化为：**从一个有理数的高精度近似值恢复其分母**——这正是连分数的经典用武之地。

### 连分数算法：从测量值中提取 r

**连分数展开**（continued fraction）是将有理数表示为嵌套分数的标准工具。对任意正有理数 $x/y$，其连分数展开为：

$$\frac{x}{y} = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cdots + \cfrac{1}{a_k}}}$$

记作 $[a_0; a_1, a_2, \ldots, a_k]$，其中 $a_i$ 为正整数（$a_0$ 可为 0）。逐级截断得到的分数 $p_t/q_t = [a_0; a_1, \ldots, a_t]$ 称为渐近分数（convergent）。

**展开算法**是欧几里得辗转相除法的直接改写：$a_0 = \lfloor x/y \rfloor$，对余数 $x \bmod y$ 与 $y$ 重复同样操作，直到余数为 0。整个过程在 $O((\log N)^3)$ 时间内完成。

**为什么连分数能恢复 $r$（Legendre 定理）**：若分数 $p/q$（既约）满足 $|\alpha - p/q| < \frac{1}{2q^2}$，则 $p/q$ 必为 $\alpha$ 的某个渐近分数。把上一节的结果代入：$j_c/Q$ 与 $c/r$ 的偏差小于 $\frac{1}{2N^2} < \frac{1}{2r^2}$；将 $c/r$ 化为既约分数 $c'/r'$（$r' = r/\gcd(c, r)$ 整除 $r$），偏差进一步小于 $\frac{1}{2r'^2}$。于是 $c'/r'$ 必然出现在 $j_c/Q$ 的渐近分数序列中。

**恢复流程**：对测量值 $j$ 做连分数展开，列出分母不超过 $N$ 的所有渐近分数分母 $q_t$ 作为候选。由于 $r' \mid r$ 且 $a^{r} \equiv 1 \pmod N$，候选中若有某个 $q$ 使 $a^{q} \equiv 1 \pmod{N}$（用快速模幂验证，代价多项式），它就是阶的一个因子。完整的后处理为：

1. 若某候选 $q_t$ 满足 $a^{q_t} \equiv 1 \pmod N$：取其中最小者，它就是 $r$（阶是最小的这样的正指数）；
2. 若候选 $q_t$ 都不满足（这发生在 $\gcd(c, r) > 1$、既约分母 $r' < r$ 时）：依次尝试 $q_t$ 的 2 倍、3 倍等小倍数并验证，因为 $r = \gcd(c,r) \cdot r'$ 是 $r'$ 的小倍数；
3. 若仍失败或测得 $j = 0$（对应 $c = 0$，不含信息）：重跑量子部分。多次运行取候选的最小公倍数也是常用策略。

**计算实例**（$N = 15$，$Q = 2^8 = 256$，$a = 7$，$r = 4$；此时 $r \mid Q$，四个峰 $j_c = 64c$ 均为整数，每个以概率 $M/Q = 1/4$ 测得）：

- 测得 $j = 192$：做辗转相除 $256 = 1 \times 192 + 64$，$192 = 3 \times 64 + 0$，故 $192/256 = [0; 1, 3]$，渐近分数依次为 $0/1,\; 1/1,\; 3/4$。候选分母 $\{1, 4\}$ 中验证：$7^1 = 7 \not\equiv 1 \pmod{15}$，候选 1 不通过；$7^4 = 2401 \equiv 1 \pmod{15}$ ✓，故 $r = 4$，提取成功（此时 $c = 3$）。
- 测得 $j = 64$：$64/256 = [0; 4]$，渐近分数为 $0/1,\; 1/4$，同样得到候选 $r = 4$，验证通过（此时 $c = 1$）。
- 测得 $j = 128$：$128/256 = [0; 2]$，渐近分数为 $0/1,\; 1/2$，候选 $r' = 2$。但 $7^2 = 49 \equiv 4 \not\equiv 1 \pmod{15}$，验证失败；改试倍数 $2 \times 2 = 4$：$7^4 \equiv 1 \pmod{15}$ ✓，故 $r = 4$。（这里 $c = 2$ 与 $r = 4$ 有公因子 2，既约分母 $2 = r/2$，正是上述第 2 种情形。）
- 测得 $j = 0$：对应 $c = 0$，不含信息，重跑。

## 量子电路结构

![Shor 算法量子电路](../circuits/shor-circuit.png)

以 $N = 15,\; a = 7$ 为例：把 $x$ 按二进制分解 $x = x_0 + 2 x_1 + 4 x_2 + \cdots$，模幂 $a^x$ 就分解为一系列受控模乘，第 $k$ 个受控门在控制比特为 1 时对目标寄存器执行 $|y\rangle \mapsto |a^{2^k} y \bmod N\rangle$。所需的乘数依次为 $7^{2^0} \bmod 15 = 7$、$7^{2^1} \bmod 15 = 4$、$7^{2^2} \bmod 15 = 1$——第三个受控门退化为恒等操作，因为 $r = 4$ 整除 $2^2$，$a^{2^2} = a^4 \equiv 1$。这正体现了周期结构：一旦指数超过周期，乘数就开始循环。

## 具体例子：分解 N = 15

1. 随机选 $a = 7$，$\gcd(7, 15) = 1$
2. 量子求阶：
   - $7^1 = 7$
   - $7^2 = 49 \equiv 4 \pmod{15}$
   - $7^3 = 343 \equiv 13 \pmod{15}$
   - $7^4 = 2401 \equiv 1 \pmod{15}$
   - 故 $r = 4$
3. $r$ 为偶数，$7^{4/2} = 7^2 = 49 \equiv 4 \not\equiv -1 \pmod{15}$
4. 计算 $\gcd(4 - 1,\; 15) = \gcd(3, 15) = \mathbf{3}$
5. 计算 $\gcd(4 + 1,\; 15) = \gcd(5, 15) = \mathbf{5}$
6. 得到：$\mathbf{15 = 3 \times 5}$

## 复杂度分析

| 步骤 | 复杂度 |
|------|--------|
| 模幂运算（量子） | $O((\log N)^3)$ 量子门 |
| 量子傅里叶变换 | $O((\log N)^2)$ 量子门 |
| 经典连分数展开 | $O((\log N)^3)$ |
| **总体** | $\mathbf{O((\log N)^3)}$ |

对比经典最优算法的亚指数复杂度，这是指数级加速。

## 当前进展与局限

**已实现的里程碑：**

- 2001 年，IBM 在 7 量子比特的量子计算机上用 Shor 算法分解了 15
- 2019 年，Google 实现了 53 量子比特的量子优越性（Sycamore）
- 2023 年起，各类量子纠错码取得实质性进展

**现实挑战：**

- 分解 2048 位 RSA 需要约 4000 个逻辑量子比特，考虑纠错开销需要数百万个物理量子比特
- 当前最先进的量子处理器约 1000+ 物理量子比特
- 量子退相干和门错误率仍是核心瓶颈

## 对密码学的影响

虽然量子计算机短期内还无法运行实用规模的 Shor 算法，但威胁已经推动了后量子密码学（Post-Quantum Cryptography）的发展：

- NIST 已于 2024 年标准化首批后量子算法（ML-KEM、ML-DSA 等）
- "现在截获、未来解密"（Harvest Now, Decrypt Later）是现实威胁
- 从 RSA/ECC 迁移到后量子算法需要数年至数十年的过渡期

## 总结

Shor 算法展示了量子计算在特定问题上相对于经典计算的指数级优势。它的推导链条环环相扣：因数分解归约为求阶；求阶归约为"用 QFT 测出 $c/r$ 的近似 $j/Q$"；连分数定理保证能从近似值恢复分母；平方差分解与最大性论证保证阶能还原出因子。理解它不仅有助于把握量子计算的本质——利用量子叠加与干涉实现并行计算——也让我们认识到量子时代对现代密码体系的深远影响。

---

**参考文献：**

1. Shor, P. W. (1994). *Algorithms for quantum computation: discrete logarithms and factoring.* FOCS 1994.
2. Nielsen, M. A., & Chuang, I. L. (2010). *Quantum Computation and Quantum Information.* Cambridge University Press.
3. NIST (2024). *Post-Quantum Cryptography Standardization.* https://csrc.nist.gov/projects/post-quantum-cryptography
---

> 返回目录：[量子计算算法教程系列](https://chenzhaoyun.com/index.php/archives/54/)