🍊柑橘 RSS 阅读器 - 鸿蒙首款原生 RSS 阅读器

如果说 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\) 可能非常长，遍历计算需要指数级时间。

量子计算机利用叠加态和量子傅里叶变换 (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 的直觉 图：QFT 将周期性的”梳状”叠加态转换为频域的尖峰，测量后可反推出周期 r。

QFT 的直觉理解： - 把 QFT 想象成”频谱分析仪”——它能识别输入信号中的周期性模式 - 如果输入是周期为 \(r\) 的”梳状”叠加态，QFT 后测量结果会集中在 \(k \cdot (M/r)\) 附近 - 通过连分数算法，可以从测量结果反推出周期 \(r\)

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

3.3 从测量值到周期：连分数算法

QFT 后测量寄存器 1 得到的整数 \(y\)，与周期 \(r\) 之间的关系是：\(y/M \approx k/r\)，其中 \(k\) 是某个整数，\(M\) 是寄存器 1 的总状态数（\(M = 2^n\)）。

问题在于：我们知道 \(y\) 和 \(M\)，但需要从 \(y/M\) 这个”近似分数”中恢复出分母 \(r\)。这正是连分数展开（Continued Fraction Expansion）的拿手好戏。

连分数算法的基本思路是：

计算 \(y/M\) 的连分数展开：\(y/M = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cdots}}\)
依次取连分数的各阶收敛子（convergent），即 \(p_0/q_0, p_1/q_1, p_2/q_2, \dots\)
其中某个收敛子的分母 \(q_i\) 就是我们要找的周期 \(r\)（或 \(r\) 的因子）。

例如，如果 \(M = 256\)，测量得到 \(y = 64\)，那么 \(y/M = 64/256 = 1/4\)，连分数展开直接给出分母 \(r = 4\)。实际情况中，\(y/M\) 通常不是精确分数，但连分数算法能够高效地找到最佳的有理数逼近。

3.4 经典后处理与失败重试

找到候选周期 \(r\) 后，还需要经典计算机做几步验证：

验证周期：检查 \(a^r \equiv 1 \pmod{N}\) 是否成立。如果不成立，可能是因为连分数给出的是 \(r\) 的因子而非 \(r\) 本身，可以尝试 \(r\) 的小倍数。
检查可用性：即使 \(r\) 正确，也有两种情况会导致本轮失败：

\(r\) 是奇数：此时 \(a^{r/2}\) 不是整数，无法使用公式 \(\gcd(a^{r/2} \pm 1, N)\)。
\(a^{r/2} \equiv -1 \pmod{N}\)：此时 \(\gcd(a^{r/2} + 1, N) = N\)，得到的是平凡因子，没有帮助。

如果失败，重新选择 \(a\)：数论告诉我们，对于随机选取的 \(a\)，至少有 \(1/2\) 的概率得到一个有效的偶数周期 \(r\)，使得 \(a^{r/2} \not\equiv -1 \pmod{N}\)。因此，只需重试几次就能以极高概率成功。

综合来看，Shor 算法整体的成功概率是很高的：数论分析表明，对于随机选取的 \(a\)，得到有效偶数周期的概率为常数级（通常需要重复若干轮即可成功）。因此，整个算法只需少量重试就能以极高概率分解 \(N\)。

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 后的测量得到一个与 \(k/r\) 相关的数值，再经连分数算法恢复出候选周期 \(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)

这一发现直接动摇了现代密码学的基石——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. 为什么经典计算机不行？

量子计算机利用叠加态和量子傅里叶变换 (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)

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

第三步：量子干涉与 QFT

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

QFT 的直觉 图：QFT 将周期性的”梳状”叠加态转换为频域的尖峰，测量后可反推出周期 r。

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

3.3 从测量值到周期：连分数算法

QFT 后测量寄存器 1 得到的整数 \(y\)，与周期 \(r\) 之间的关系是：\(y/M \approx k/r\)，其中 \(k\) 是某个整数，\(M\) 是寄存器 1 的总状态数（\(M = 2^n\)）。

问题在于：我们知道 \(y\) 和 \(M\)，但需要从 \(y/M\) 这个”近似分数”中恢复出分母 \(r\)。这正是连分数展开（Continued Fraction Expansion）的拿手好戏。

连分数算法的基本思路是：

计算 \(y/M\) 的连分数展开：\(y/M = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cdots}}\)
依次取连分数的各阶收敛子（convergent），即 \(p_0/q_0, p_1/q_1, p_2/q_2, \dots\)
其中某个收敛子的分母 \(q_i\) 就是我们要找的周期 \(r\)（或 \(r\) 的因子）。

3.4 经典后处理与失败重试

找到候选周期 \(r\) 后，还需要经典计算机做几步验证：

验证周期：检查 \(a^r \equiv 1 \pmod{N}\) 是否成立。如果不成立，可能是因为连分数给出的是 \(r\) 的因子而非 \(r\) 本身，可以尝试 \(r\) 的小倍数。
检查可用性：即使 \(r\) 正确，也有两种情况会导致本轮失败：

\(r\) 是奇数：此时 \(a^{r/2}\) 不是整数，无法使用公式 \(\gcd(a^{r/2} \pm 1, N)\)。
\(a^{r/2} \equiv -1 \pmod{N}\)：此时 \(\gcd(a^{r/2} + 1, N) = N\)，得到的是平凡因子，没有帮助。

如果失败，重新选择 \(a\)：数论告诉我们，对于随机选取的 \(a\)，至少有 \(1/2\) 的概率得到一个有效的偶数周期 \(r\)，使得 \(a^{r/2} \not\equiv -1 \pmod{N}\)。因此，只需重试几次就能以极高概率成功。

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 后的测量得到一个与 \(k/r\) 相关的数值，再经连分数算法恢复出候选周期 \(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 的威胁

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

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

这一发现直接动摇了现代密码学的基石——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. 为什么经典计算机不行？

量子计算机利用叠加态和量子傅里叶变换 (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)

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

第三步：量子干涉与 QFT

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

QFT 的直觉 图：QFT 将周期性的”梳状”叠加态转换为频域的尖峰，测量后可反推出周期 r。

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

3.3 从测量值到周期：连分数算法

QFT 后测量寄存器 1 得到的整数 \(y\)，与周期 \(r\) 之间的关系是：\(y/M \approx k/r\)，其中 \(k\) 是某个整数，\(M\) 是寄存器 1 的总状态数（\(M = 2^n\)）。

问题在于：我们知道 \(y\) 和 \(M\)，但需要从 \(y/M\) 这个”近似分数”中恢复出分母 \(r\)。这正是连分数展开（Continued Fraction Expansion）的拿手好戏。

连分数算法的基本思路是：

计算 \(y/M\) 的连分数展开：\(y/M = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cdots}}\)
依次取连分数的各阶收敛子（convergent），即 \(p_0/q_0, p_1/q_1, p_2/q_2, \dots\)
其中某个收敛子的分母 \(q_i\) 就是我们要找的周期 \(r\)（或 \(r\) 的因子）。

3.4 经典后处理与失败重试

找到候选周期 \(r\) 后，还需要经典计算机做几步验证：

验证周期：检查 \(a^r \equiv 1 \pmod{N}\) 是否成立。如果不成立，可能是因为连分数给出的是 \(r\) 的因子而非 \(r\) 本身，可以尝试 \(r\) 的小倍数。
检查可用性：即使 \(r\) 正确，也有两种情况会导致本轮失败：

\(r\) 是奇数：此时 \(a^{r/2}\) 不是整数，无法使用公式 \(\gcd(a^{r/2} \pm 1, N)\)。
\(a^{r/2} \equiv -1 \pmod{N}\)：此时 \(\gcd(a^{r/2} + 1, N) = N\)，得到的是平凡因子，没有帮助。

如果失败，重新选择 \(a\)：数论告诉我们，对于随机选取的 \(a\)，至少有 \(1/2\) 的概率得到一个有效的偶数周期 \(r\)，使得 \(a^{r/2} \not\equiv -1 \pmod{N}\)。因此，只需重试几次就能以极高概率成功。

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 后的测量得到一个与 \(k/r\) 相关的数值，再经连分数算法恢复出候选周期 \(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 的威胁

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

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