Shor 算法求解离散对数问题详解

Shor 算法不仅能够高效分解整数，还可以在多项式时间内求解离散对数问题（Discrete Logarithm Problem, DLP）——而这正是 Diffie-Hellman 密钥交换、DSA 数字签名和椭圆曲线密码（ECC）安全性的数学基础。本文详细分析 Shor 算法在离散对数上的应用。

问题定义

离散对数问题

给定素数 \(p\)，乘法群 \(\mathbb{Z}_p^*\) 的生成元（generator）\(g\)，以及元素 \(h \in \mathbb{Z}_p^*\)，求整数 \(x\) 使得：

\[g^x \equiv h \pmod{p}\]

记作 \(x = \log_g h\)。由于 \(g\) 是生成元，其阶恰为 \(p - 1\)，因此 \(x\) 在模 \(p-1\) 意义下存在且唯一。以下记群阶 \(n = p - 1\)。

为什么重要

  • Diffie-Hellman 密钥交换：双方公开 \(g^a\) 与 \(g^b\)，共享密钥为 \(g^{ab} \bmod p\)；其安全性基于从 \(g^a\) 与 \(g^b\) 计算 \(g^{ab}\) 的困难性

  • DSA 数字签名：签名验证依赖 DLP 的困难性

  • 椭圆曲线密码（ECC）：椭圆曲线离散对数问题（ECDLP），对一般曲线目前没有经典亚指数算法

经典最优算法：

  • 一般 DLP：数域筛法（Number Field Sieve），亚指数时间 \(O\!\left(e^{(c + o(1))(\log p)^{1/3}(\log \log p)^{2/3}}\right)\)，其中 \(c = (64/9)^{1/3} \approx 1.92\)

  • ECDLP：Pollard rho 算法，\(O(\sqrt{n})\)，对 256 位曲线约为 \(O(2^{128})\)

Shor 算法求解离散对数

核心思想

Shor 的 DLP 算法将离散对数 \(x = \log_g h\) 归约为隐藏子群问题（Hidden Subgroup Problem, HSP）：考察函数 \(f(a, b) = g^a h^b \bmod p\)。由 \(h = g^x\) 可知 \(f(a, b) = g^{a + xb \bmod n}\)，它在一个二维格的每个陪集上取常值、在不同陪集上取不同值；求出这个隐藏的格，等价于求出 \(x\)。量子傅里叶变换（QFT）正是从这类"陪集常值函数"中提取隐藏子群的标准工具。

算法步骤

第一步：量子叠加制备

制备两个寄存器的均匀叠加态：

\[|\psi_0\rangle = \frac{1}{n} \sum_{a=0}^{n-1} \sum_{b=0}^{n-1} |a\rangle|b\rangle|0\rangle\]

（归一化是对的：\((p-1)^2 = n^2\) 个基态各带振幅 \(1/n = 1/\sqrt{n^2}\)。）每个寄存器有 \(\lceil\log_2 n\rceil = \lceil\log_2(p-1)\rceil\) 个量子比特。

第二步：模幂计算

计算 \(f(a, b) = g^a h^b \bmod p\)，将结果写入第三个寄存器：

\[|\psi_1\rangle = \frac{1}{n} \sum_{a,b} |a\rangle|b\rangle|g^a h^b \bmod p\rangle\]

关键性质：由 \(h = g^x\) 得 \(g^a h^b = g^a \cdot g^{xb} = g^{a + xb}\)，且 \(g\) 的阶为 \(n\)，故 \(g^u = g^v\) 当且仅当 \(u \equiv v \pmod n\)。于是 \(f(a,b)\) 只依赖于 \((a + xb) \bmod n\)：对每个 \(r \in \mathbb{Z}_n\)，\(f(a, b) = g^r\) 当且仅当 \(a + xb \equiv r \pmod n\)，其解集为

\[\{(a, b) : a + xb \equiv r \pmod{n}\} = \{(r - xb \bmod n,\; b) : b \in \mathbb{Z}_n\}\]

（把每个 \(b\) 代入解出唯一的 \(a\)，共 \(n\) 个解。）这些解集是一个固定子群的平移：集合

\[\Lambda = \{(a, b) \in \mathbb{Z}_n \times \mathbb{Z}_n : a + xb \equiv 0 \pmod{n}\}\]

对加法封闭（两个满足同余式的元素之和仍满足），是 \(\mathbb{Z}_n \times \mathbb{Z}_n\) 的子群，而解集恰为陪集 \(\Lambda + (r, 0)\)。\(f\) 在 \(\Lambda\) 的每个陪集上取常值、在不同陪集上取不同值——\(f\) 隐藏了子群 \(\Lambda\)，而 \(\Lambda\) 由 \(x\) 完全决定。

第三步：量子傅里叶变换（QFT）

对前两个寄存器施加二维 QFT：

\[\text{QFT}_n \otimes \text{QFT}_n : |a\rangle|b\rangle \to \frac{1}{n} \sum_{c=0}^{n-1} \sum_{d=0}^{n-1} e^{2\pi i(ac+bd)/n} |c\rangle|d\rangle\]

随后测量前两个寄存器。测量结果 \((c, d)\) 以均匀概率满足线性关系（完整推导见下文"理论推导"一节）

\[xc \equiv d \pmod{n}\]

于是当 \(c\) 与 \(n\) 互素时，一次解出 \(x \equiv c^{-1} d \pmod{n}\)。

第四步：经典后处理

  1. 从测量结果 \((c, d)\) 计算 \(x \equiv c^{-1} d \pmod{n}\)（用扩展欧几里得算法求 \(c^{-1}\)）

  2. 若 \(\gcd(c, n) > 1\)，将同余式两边除以 \(\gcd(c,n)\) 得到 \(x\) 模 \(n/\gcd(c,n)\) 的信息，多次测量收集多个方程后用中国剩余定理（Chinese Remainder Theorem, CRT）合并

理论推导

测量分布的完整推导

我们对第三步做完整计算。由关键性质，把 \(|\psi_1\rangle\) 按第三个寄存器的取值分组：

\[|\psi_1\rangle = \frac{1}{n} \sum_{r \in \mathbb{Z}_n} \left(\sum_{b \in \mathbb{Z}_n} |(r - xb) \bmod n\rangle |b\rangle\right) |g^r\rangle\]

内层括号正是陪集 \(\Lambda + (r, 0)\) 上 \(n\) 个基态的均匀叠加。对前两个寄存器施加 \(\text{QFT}_n \otimes \text{QFT}_n\)，由线性性，基态 \(|c\rangle|d\rangle|g^r\rangle\) 的振幅为

\[\alpha_{c,d,r} = \frac{1}{n} \cdot \frac{1}{\sqrt n} \cdot \frac{1}{\sqrt n} \sum_{b \in \mathbb{Z}_n} e^{2\pi i \left[(r - xb)c + bd\right]/n} = \frac{e^{2\pi i r c/n}}{n^2} \sum_{b \in \mathbb{Z}_n} \left(e^{2\pi i (d - xc)/n}\right)^{b}\]

其中我们把与 \(b\) 无关的因子 \(e^{2\pi i rc/n}\) 提出求和号。内层是以 \(\omega^{d - xc}\)（\(\omega = e^{2\pi i /n}\)）为公比的几何级数，用等比求和公式：

  • 若 \(d \equiv xc \pmod{n}\)，每项都是 1，级数等于 \(n\)；

  • 若 \(d \not\equiv xc \pmod{n}\)，则 \(e^{2\pi i(d - xc)/n} \neq 1\) 而 \(\left(e^{2\pi i(d - xc)/n}\right)^n = e^{2\pi i(d - xc)} = 1\)，级数等于 \(\frac{1 - 1}{e^{2\pi i(d-xc)/n} - 1} = 0\)。

因此振幅非零当且仅当 \(xc \equiv d \pmod n\)；非零时其模为 \(n / n^2 = 1/n\)。对 \(r\) 求和（\(r\) 只出现在相位因子中，不影响模长），测得满足 \(xc \equiv d\) 的 \((c, d)\) 的概率为 \(n \cdot (1/n)^2 = 1/n\)。满足条件的 \((c,d)\) 恰有 \(n\) 个（每个 \(c\) 唯一对应 \(d = xc \bmod n\)），概率总和为 1。结论：

\[(c, d) \text{ 均匀分布于 } \{(c,\; xc \bmod n) : c \in \mathbb{Z}_n\}，\quad \text{恒有 } xc \equiv d \pmod{n}\]

特别地，\(c\) 在 \(\mathbb{Z}_n\) 上均匀分布。

格结构分析

\(\mathbb{Z}_n \times \mathbb{Z}_n\) 中满足 \(a + xb \equiv 0 \pmod{n}\) 的点集 \(\Lambda\) 也可以看成 \(\mathbb{Z}^2\) 中的二维格（lattice），它的一组基为：

\[\Lambda = \text{span}_{\mathbb{Z}}\{(n, 0),\; (-x, 1)\}\]

验证：\((n, 0)\)：\(n + x \cdot 0 = n \equiv 0 \pmod{n}\) ✓；\((-x, 1)\)：\(-x + x \cdot 1 = 0 \equiv 0 \pmod{n}\) ✓。反过来，任一整系数组合 \(m(n, 0) + l(-x, 1) = (mn - lx,\; l)\) 都满足 \((mn - lx) + x \cdot l \equiv 0 \pmod n\)，且这样的组合互不相同地覆盖了 \(\Lambda\) 的全部 \(n\) 个元素（\(l = b\) 取遍 \(\mathbb{Z}_n\)，每个 \(b\) 给出唯一的 \(a = -lx \bmod n\)），故上述两向量确为 \(\Lambda\) 的基。基中向量 \((-x, 1)\) 直接包含未知量 \(x\)——求出 \(\Lambda\) 就等于求出 \(x\)。

上一节的测量结果集 \(\{(c,\, xc \bmod n)\}\) 恰是 \(\Lambda\) 的（模 \(n\) 意义下的）对偶格（dual lattice）\(\Lambda^* = \{(c, d) : ac + bd \equiv 0 \pmod n,\ \forall (a,b) \in \Lambda\}\)：条件对基向量 \((n, 0)\) 自动成立（\(nc \equiv 0\)），对 \((-x, 1)\) 给出 \(-xc + d \equiv 0\)，即 \(d \equiv xc\)——与推导结果完全一致。这正是隐藏子群问题中"QFT 采样得到对偶格元素"的一般规律。

成功概率与不可逆情形的处理

\(c\) 均匀分布于 \(\mathbb{Z}_n\)，故单次测量得到 \(\gcd(c, n) = 1\)（从而 \(c^{-1}\) 存在、一次解出 \(x\)）的概率为 \(\phi(n)/n\)，其中 \(\phi\) 为欧拉函数（Euler's totient function）。注意 \(n = p - 1\) 是偶数（\(p\) 为奇素数），必然是合数，因此 \(\phi(n)/n = \prod_{\ell \mid n} \left(1 - \frac{1}{\ell}\right)\) 严格小于 1；例如 \(n = 12 = 2^2 \cdot 3\) 时 \(\phi(12)/12 = \frac{1}{2} \cdot \frac{2}{3} = \frac{1}{3}\)。

若测得 \(g_0 = \gcd(c, n) > 1\)，也不必丢弃这次结果。同余式 \(xc \equiv d \pmod n\) 意味着 \(n \mid d - xc\)；由于 \(g_0 \mid n\) 且 \(g_0 \mid c\)（从而 \(g_0 \mid xc\)），可得 \(g_0 \mid d\)。于是写 \(c = g_0 c'\)、\(n = g_0 n'\)、\(d = g_0 d'\)，同余式两边除以 \(g_0\) 得到合法的同余式

\[c' x \equiv d' \pmod{n'}, \qquad d' = d / g_0,\; n' = n / g_0\]

此时 \(\gcd(c', n') = 1\)，解得 \(x \bmod n'\)。多次测量得到 \(x\) 模 \(n\) 的各个"分量"后，用中国剩余定理合并即可恢复 \(x \bmod n\)。

数值实例：p = 13，g = 2，h = 11

取 \(p = 13\)，则 \(n = 12\)。\(2\) 是 \(\mathbb{Z}_{13}^*\) 的生成元（逐一计算 \(2^1, 2^2, \ldots, 2^{12} = 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1\)，阶为 12）。设隐藏的 \(x = 7\)，则 \(h = g^7 = 2^7 = 128 \equiv 11 \pmod{13}\)。

量子部分给出的每次测量结果是满足 \(7c \equiv d \pmod{12}\) 的均匀随机对 \((c, d)\)。下表列出几组典型结果与经典后处理：

测得 \(c\)

对应 \(d = 7c \bmod 12\)

\(\gcd(c, 12)\)

后处理

1

7

1

\(x \equiv 1^{-1} \cdot 7 = 7 \pmod{12}\) ✓

5

11

1

\(5^{-1} \equiv 5\)（\(5 \times 5 = 25 \equiv 1\)），\(x \equiv 5 \times 11 = 55 \equiv 7\) ✓

7

1

1

\(7^{-1} \equiv 7\)（\(7 \times 7 = 49 \equiv 1\)），\(x \equiv 7 \times 1 = 7\) ✓

11

5

1

\(11^{-1} \equiv 11\)（\(11 \times 11 = 121 \equiv 1\)），\(x \equiv 11 \times 5 = 55 \equiv 7\) ✓

2

2

2

除以 2：\(x \equiv 1 \pmod 6\)，即 \(x \in \{1, 7\}\)，需再测一次合并

单次测量直接成功的概率为 \(\phi(12)/12 = 4/12 = 1/3\)（\(c \in \{1, 5, 7, 11\}\) 时可逆）；即便测到不可逆的 \(c\)，也能像最后一行那样缩小候选范围，再测一次即可确定。最终验证：\(2^7 = 128 = 9 \times 13 + 11 \equiv 11 \pmod{13}\) ✓。

对椭圆曲线的推广

Shor 算法可以直接推广到椭圆曲线离散对数问题（ECDLP）：

给定椭圆曲线 \(E\)，基点 \(G\)，点 \(H = xG\)，求 \(x\)。

量子电路修改：

  • 模幂运算替换为椭圆曲线点乘：\(|a\rangle|b\rangle|0\rangle \to |a\rangle|b\rangle|aG + bH\rangle\)

  • QFT 在椭圆曲线群的阶 \(n\) 上进行

  • 其余步骤完全相同

复杂度：\(O(\text{poly}(\log n))\) 量子门，与经典 \(O(\sqrt{n})\) 相比为指数加速。

与整数分解的关系

Shor 的两个算法共享同一个量子内核，但并不是一个归约为另一个。

一方面，整数分解被归约为一维周期查找：给定 \(a\) 与 \(N\)，函数 \(x \mapsto a^x \bmod N\) 以阶 \(r\) 为周期，求出 \(r\) 即可按本文因数分解篇的方式分解 \(N\)。另一方面，离散对数是二维周期查找：函数 \(f(a, b) = g^a h^b\) 在二维格 \(\Lambda\) 的每个陪集上取常值，求出 \(\Lambda\) 的基即得 \(x\)。

两者都可以纳入阿贝尔隐藏子群问题的统一框架：给定群 \(G\) 与在子群 \(H\) 的每个陪集上取常值、不同陪集取不同值的函数 \(f\)，求 \(H\)；解法是对 \(f\) 的定义域做量子傅里叶采样，从对偶对象中读出 \(H\)。本教程系列中的 BV 算法（\(G = \mathbb{Z}_2^n\)，线性结构）、Simon 算法（\(G = \mathbb{Z}_2^n\)，异或周期）、求阶（\(G = \mathbb{Z}\)）、离散对数（\(G = \mathbb{Z} \times \mathbb{Z}\)）都是这一框架的实例。

反方向的归约——把离散对数归约为整数分解——目前没有已知的多项式时间算法。两个问题在经典模型下互不归约，却在量子模型下被同一套傅里叶采样技术一并击破。

对密码学的影响

密码系统

依赖问题

Shor 量子威胁

RSA

整数分解

\(O((\log N)^3)\) 时间破解

Diffie-Hellman

DLP

\(O((\log p)^3)\) 时间破解

DSA

DLP

\(O((\log p)^3)\) 时间破解

ECC

ECDLP

\(O((\log n)^3)\) 时间破解

所有主流公钥密码系统都受 Shor 算法威胁。ECC 虽然经典安全性更高（256 位 ECC ≈ 3072 位 RSA），但对量子攻击同样脆弱。

复杂度分析

步骤

量子门数

模幂运算 \(g^a h^b\)

\(O((\log p)^3)\)

二维 QFT

\(O((\log p)^2)\)

经典后处理

\(O((\log p)^3)\)

总计

\(O((\log p)^3)\)

对比经典：

方法

复杂度

数域筛法（DLP）

\(O(e^{c(\log p)^{1/3}(\log\log p)^{2/3}})\)

Pollard rho（ECDLP）

\(O(\sqrt{n})\)

Shor（量子）

\(O(\text{poly}(\log p))\)

总结

Shor 算法对离散对数的求解，连同整数分解，构成了对所有主流公钥密码系统的统一量子威胁。对椭圆曲线密码的威胁尤其值得关注：ECC 被广泛部署在移动设备、IoT 和区块链中，其经典安全边际远低于 RSA，因此对量子攻击更加脆弱。这也是后量子密码标准化的紧迫动因之一。

参考文献：

  1. Shor, P. W. (1994). Algorithms for quantum computation: discrete logarithms and factoring. FOCS 1994.

  2. Proos, J., & Zalka, C. (2003). Shor's discrete logarithm quantum algorithm for elliptic curves. Quantum Information & Computation, 3(4), 317-344.

  3. NIST (2024). Post-Quantum Cryptography Standardization. https://csrc.nist.gov/projects/post-quantum-cryptography

  4. Roetteler, M., Naehrig, M., Svore, K. M., & Lauter, K. (2017). Quantum resource estimates for computing elliptic curve discrete logarithms. ASIACRYPT 2017.