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

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

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

$$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$，若 $r$ 为偶数且 $a^{r/2} \not\equiv -1 \pmod{N}$，则 $\gcd(a^{r/2} \pm 1,\; N)$ 以高概率给出 $N$ 的一个非平凡因子。

算法步骤

第一步：经典预处理

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

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

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

• 寄存器 1：$n = \lceil \log_2 N^2 \rceil$ 个量子比特，用于存储 $x$ 的叠加态
• 寄存器 2：用于存储 $a^x \bmod N$ 的结果

操作流程：

1. 初始化寄存器 1 为等权叠加态：$|\psi\rangle = \frac{1}{\sqrt{2^n}} \sum_{x=0}^{2^n-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 施加量子傅里叶变换（QFT）：$\text{QFT}: |j\rangle \mapsto \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} e^{2\pi i jk / 2^n} |k\rangle$

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

6. 用连分数展开从测量结果中提取 $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：若 $r$ 为偶数且 $a^{r/2} \not\equiv -1 \pmod{N}$，则 $\gcd(a^{r/2} - 1,\; N)$ 和 $\gcd(a^{r/2} + 1,\; N)$ 中至少有一个是 $N$ 的非平凡因子。

证明：由阶的定义，$a^r \equiv 1 \pmod{N}$，即 $N \mid (a^r - 1)$。利用平方差公式：

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

因此 $N$ 整除该乘积，即 $N \mid (a^{r/2} - 1)(a^{r/2} + 1)$。

接下来证明 $(a^{r/2} - 1)$ 和 $(a^{r/2} + 1)$ 互素。它们的差为 2，因此：

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

因为 $N$ 是奇数（若 $N$ 为偶数可直接被 2 整除，无需 Shor 算法），$N$ 的所有素因子都是奇数。所以 $N$ 的素因子不可能同时整除 $(a^{r/2} - 1)$ 和 $(a^{r/2} + 1)$。

这意味着 $N$ 的素因子被”分配”到了两个因子中——某些整除 $(a^{r/2} - 1)$，其余整除 $(a^{r/2} + 1)$。只要 $a^{r/2} \not\equiv \pm 1 \pmod{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\}$ 被分别”捕获”

失败条件分析：算法失败有两种情况。

1. $r$ 为奇数：若 $N = pq$，则 $r = \text{lcm}(\text{ord}_p(a),\; \text{ord}_q(a))$。当 $p - 1$ 和 $q - 1$ 都有大量 2 的因子时（RSA 素数正是如此设计的），$r$ 为奇数的概率很低，约为 $1/2^k$（$k$ 为 2 的幂次最小值）。

2. $a^{r/2} \equiv -1 \pmod{N}$：这意味着 $a^{r/2} \equiv -1 \pmod{p}$ 且 $a^{r/2} \equiv -1 \pmod{q}$ 同时成立。对随机选取的 $a$，这两个同余式同时成立的概率约为 $1/4$。

综合两种失败情况，单次成功的概率至少约为 $1/2$。重复 $k$ 次后失败概率降至 $1/2^k$。

QFT 提取周期的数学原理

测量寄存器 2 得到 $y$ 后，寄存器 1 坍缩为所有满足 $a^x \equiv y \pmod{N}$ 的 $|x\rangle$ 的等权叠加态：

$$|\phi\rangle = \frac{1}{\sqrt{M}} \sum_{k=0}^{M-1} |x_0 + kr\rangle$$

其中 $M = \lfloor (2^n - 1 - x_0)/r \rfloor \approx 2^n / r$ 是满足条件的项数。

对 $|\phi\rangle$ 施加 QFT，展开定义并交换求和顺序，对固定的 $j$，振幅为：

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

令 $\Delta = jr / 2^n$，内层求和是一个公比为 $e^{2\pi i \Delta}$ 的几何级数。当 $\Delta$ 接近整数时（即 $jr$ 接近 $2^n$ 的整数倍），几何级数的项几乎同相，产生相长干涉，概率出现峰值。

令 $c$ 为最接近 $jr/2^n$ 的整数，定义偏差 $\delta = jr/2^n - c$。几何级数的模为：

$$|\Sigma| = \frac{|\sin(\pi M \delta)|}{|\sin(\pi \delta)|}$$

当 $|\delta| < 1/(2M) \approx r/2^{n+1}$ 时，$\sin(\pi M\delta)/\sin(\pi\delta) \approx M$，概率达到峰值。

因此测量结果 $j$ 以高概率满足：

$$\left|\frac{jr}{2^n} - c\right| < \frac{1}{2}$$

两边除以 $r$ 并乘以 $2^n$ 得：

$$\left|j - c \cdot \frac{2^n}{r}\right| < \frac{2^n}{2r}$$

即 $j$ 以高概率落在 $c \cdot 2^n / r$ 的 $\pm 1/2$ 邻域内，其中 $c \in \{0, 1, \ldots, r-1\}$。换言之，测量值 $j/2^n$ 近似等于某个以 $r$ 为分母的有理数 $c/r$，问题转化为：从一个有理数的近似值恢复分母。

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

连分数展开是将有理数表示为嵌套分数的标准工具。对任意正有理数 $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）。

算法（Euclidean 算法变体）：对 $j/2^n$ 做连分数展开，在展开过程中取渐近分数 $p_t / q_t$，直到分母 $q_t > N$。在所有满足 $q_t \le N$ 的渐近分数中，若某个 $q_t$ 恰好等于 $r$，则成功。

正确性保证：由测量值的性质，$|j/2^n - c/r| < 1/(2 \cdot 2^n)$。根据连分数的逼近理论，若一个有理数 $p/q$ 满足 $|\alpha - p/q| < 1/(2q^2)$，则 $p/q$ 必为 $\alpha$ 的某个渐近分数。由于 $r < N < 2^n$，条件 $|j/2^n - c/r| < 1/(2r^2)$ 成立，$r$ 必然出现在渐近分数序列中。

计算实例（$N = 15,\; n = 8,\; a = 7,\; r = 4$）：

假设测量结果 $j = 192$（$= 3/4 \times 256$ 的最近整数），做连分数展开：$192/256 = [0; 1, 3]$，渐近分数为 $0/1,\; 1/1,\; \mathbf{3/4}$。分母 $4 = r$，提取成功。此时 $c = 3$，验证：$\gcd(7^2 \pm 1,\; 15)$ 给出因子。

若 $j = 64$（$= 1/4 \times 256$），则 $64/256 = [0; 4]$，渐近分数为 $0/1,\; \mathbf{1/4}$，同样得到 $r = 4$。

量子电路结构

以 $N = 15,\; a = 7$ 为例，每个受控门对目标寄存器执行模乘 $|y\rangle \mapsto |a^{2^k} y \bmod N\rangle$：乘数依次为 $7 \bmod 15 = 7$、$7^2 \bmod 15 = 4$、$7^3 \bmod 15 = 13$。

具体例子：分解 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}$

复杂度分析

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

当前进展与局限

已实现的里程碑：

• 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 算法展示了量子计算在特定问题上相对于经典计算的指数级优势。理解它不仅有助于把握量子计算的本质——利用量子叠加与干涉实现并行计算——也让我们认识到量子时代对现代密码体系的深远影响。

参考文献：

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