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 算法量子电路

以 \(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