量子计算如何分解质因子：Shor 算法详解

如果说 Grover 算法是量子计算的“瑞士军刀”（加速搜索），那么 Shor 算法就是量子计算的“核武器”。它由 Peter Shor 在 1994 年提出，证明了量子计算机可以在多项式时间内分解大整数。

这一发现直接动摇了现代密码学的基石——RSA 加密体系。本文将带你理解 Shor 算法是如何一步步“拆解”质因数的。

1. 问题的本质：从分解到周期查找

对于经典计算机，分解大整数 \(N\)（例如 \(N = p \times q\)）是非常困难的。目前最好的经典算法（数域筛法 GNFS）其复杂度也是亚指数级的。

Shor 的天才之处在于，他没有直接去硬算因子，而是将因数分解问题转化为了周期查找问题 (Period Finding)。

1.1 欧拉定理与周期

对于我们要分解的整数 \(N\)，随机选一个小于 \(N\) 的整数 \(a\)（且 \(\gcd(a, N) = 1\)）。考虑函数： \[ f(x) = a^x \pmod N \]

这个函数是周期性的。如果我们能找到最小的正整数 \(r\)（周期），使得： \[ a^r \equiv 1 \pmod N \]

那么根据数论性质，如果 \(r\) 是偶数，我们就有很大概率通过以下公式找到 \(N\) 的因子： \[ \text{Factors} = \gcd(a^{r/2} \pm 1, N) \]

结论：只要能快速找到周期 \(r\)，就能快速分解 \(N\)。

2. 为什么经典计算机不行？

寻找周期 \(r\) 在经典计算机上并不容易。你需要计算 \(a^1, a^2, a^3, \dots \pmod N\) 直到结果为 1。对于很大的 \(N\)，这个周期 \(r\) 可能非常长，遍历计算需要指数级时间。

3. Shor 算法的核心流程

量子计算机利用叠加态和量子傅里叶变换 (QFT)，可以一次性分析函数的整体结构，从而快速提取出周期 \(r\)。

3.1 算法步骤

Shor 算法是一个混合算法，包含经典部分和量子部分。

graph TD
    Start[开始: 待分解整数 N] --> Step1[经典: 随机选 a < N]
    Step1 --> Step2[经典: 检查 gcd(a, N)]
    Step2 -- gcd > 1 --> Found[运气好: 直接找到因子]
    Step2 -- gcd = 1 --> Quantum[进入量子部分]
    
    subgraph Quantum Routine
    Q1[制备叠加态] --> Q2[模幂运算 U_f: |x>|a^x mod N>]
    Q2 --> Q3[测量第二寄存器]
    Q3 --> Q4[对第一寄存器做 QFT]
    Q4 --> Q5[测量第一寄存器得到 y]
    end
    
    Quantum --> ClassicalPost[经典后处理: 利用连分数求 r]
    ClassicalPost --> Check[检查 r 是否有效]
    Check -- 奇数或无效 --> Step1
    Check -- 有效 --> Result[计算 gcd(a^(r/2)±1, N)]

3.2 关键量子步骤详解

第一步：制备叠加态

我们需要两个量子寄存器。 * 寄存器 1：用于存放指数 \(x\)，初始化为所有可能的 \(x\) 的均匀叠加态。 * 寄存器 2：用于存放计算结果 \(f(x)\)。

\[ |\psi_0\rangle = \frac{1}{\sqrt{M}} \sum_{x=0}^{M-1} |x\rangle |0\rangle \]

第二步：模幂运算 (Modular Exponentiation)

这是算法中最耗时的部分。我们设计一个量子电路，计算 \(f(x) = a^x \pmod N\) 并存入寄存器 2。由于寄存器 1 处于叠加态，这一步实际上并行计算了所有可能的 \(a^x\)。

\[ |\psi_1\rangle = \frac{1}{\sqrt{M}} \sum_{x=0}^{M-1} |x\rangle |a^x \pmod N\rangle \]

第三步：量子干涉与 QFT

这是见证奇迹的时刻。虽然寄存器 1 中包含了所有 \(x\)，但我们不能直接测量，否则只能得到一个随机的 \(x\)，毫无意义。

我们需要提取的是这些态之间的周期性结构。 1. 当我们（概念上）测量寄存器 2 得到某个值 \(y_0\) 时，寄存器 1 就坍缩成了所有满足 \(a^x \pmod N = y_0\) 的 \(x\) 的叠加。这些 \(x\) 恰好相差周期 \(r\)（即 \(x_0, x_0+r, x_0+2r \dots\)）。 2. 此时，寄存器 1 的波函数就像是一个梳状函数（Comb Function），齿距为 \(r\)。 3. 对寄存器 1 应用 量子傅里叶变换 (QFT)。QFT 会将时域上的周期 \(r\) 转换为频域上的峰值。

测量经过 QFT 后的寄存器 1，我们有很大概率得到一个与 \(1/r\) 相关的整数。

4. 实例演示：分解 15

假设我们要分解 \(N=15\)。

选择 a: 选 \(a=7\)（与 15 互质）。
量子计算: 寻找 \(f(x) = 7^x \pmod{15}\) 的周期。
- \(7^1 \equiv 7\)
- \(7^2 = 49 \equiv 4\)
- \(7^3 = 343 \equiv 13\)
- \(7^4 \equiv 1\) <– 周期 r = 4
量子测量: 量子计算机通过 QFT 告诉我们 \(r=4\)。
经典计算:
- \(r\) 是偶数，计算 \(x = a^{r/2} = 7^2 = 49 \equiv 4 \pmod{15}\)。
- 计算最大公约数：
  - \(\gcd(x-1, N) = \gcd(3, 15) = 3\)
  - \(\gcd(x+1, N) = \gcd(5, 15) = 5\)
结果: 因子为 3 和 5。分解成功！

5. 对 RSA 的威胁

RSA 加密的安全性依赖于 \(N=p \times q\) 难以分解。 * 经典复杂度: \(O(e^{C (\log N)^{1/3} (\log \log N)^{2/3}})\) （亚指数级）。 * Shor 算法复杂度: \(O((\log N)^3)\) （多项式级）。

这意味着，只要有足够多且稳定的量子比特（数千个逻辑量子比特，可能需要数百万物理量子比特用于纠错），现有的 RSA-2048 可以在几小时内被破解，而经典超级计算机可能需要宇宙寿命的时间。

这也是为什么 NIST 正在加急标准化 后量子密码学 (PQC) 的原因。

上一篇: quantum_algorithm_construction.md - 量子算法构造 延伸阅读: ../../crypt/PQC/pqc.md - 后量子密码学 (PQC)

目录