Shor 算法求解离散对数问题详解¶
Shor 算法不仅能够高效分解整数，还可以在多项式时间内求解离散对数问题（Discrete Logarithm Problem, DLP）——而这正是 Diffie-Hellman 密钥交换、DSA 数字签名和椭圆曲线密码（ECC）安全性的数学基础。本文详细分析 Shor 算法在离散对数上的应用。
本课知识点
离散对数问题与密码学背景——能写出离散对数问题的输入与输出，解释解为何在模 \(p-1\) 意义下存在且唯一，并列出依赖其困难性的三类密码系统及经典最优算法的复杂度量级。
隐藏子群归约——能把 \(f(a, b) = g^a h^b\) 的取值化简为 \(g^{a + xb \bmod n}\)，并解释"\(f\) 在隐藏子群 \(\Lambda\) 的每个陪集上取常值、在不同陪集上取不同值"如何把求 \(x\) 归约为隐藏子群问题。
算法四步流程——能按顺序写出叠加制备、模幂计算、QFT 与经典后处理四步中各寄存器的量子态，并推导 \(f(a, b)\) 的每个等值集都是陪集 \(\Lambda + (r, 0)\)。
测量分布的完整推导——能用等比级数求和完成 QFT 后振幅的计算，证明振幅非零当且仅当 \(xc \equiv d \pmod{n}\)，并推出 \((c, d)\) 均匀分布于 \(\{(c,\, xc \bmod n)\}\)。
格结构与对偶格——能验证 \(\{(n, 0),\, (-x, 1)\}\) 是隐藏格 \(\Lambda\) 的一组基，并证明测量结果集 \(\{(c,\, xc \bmod n)\}\) 恰为对偶格 \(\Lambda^*\)。
成功概率与 CRT 后处理——能计算单次测量直接解出 \(x\) 的概率 \(\phi(n)/n\)，并对 \(\gcd(c, n) > 1\) 的结果推导约化同余式 \(c'x \equiv d' \pmod{n'}\)，说明用中国剩余定理合并多次测量的流程。
数值实例：p = 13——能对 \(p = 13\)、\(g = 2\)、\(h = 11\) 独立复演从测量对 \((c, d)\) 恢复 \(x = 7\) 的经典后处理，包括 \(\gcd(c, 12) > 1\) 时的候选集缩减。
对椭圆曲线的推广——能写出 ECDLP 版本中被替换的两个组件（椭圆曲线点乘替换模幂、QFT 改在曲线群的阶上进行），并比较量子多项式复杂度与经典 Pollard rho 的 \(O(\sqrt{n})\)。
问题定义¶
离散对数问题¶
给定素数 \(p\)，乘法群 \(\mathbb{Z}_p^*\) 的生成元（generator）\(g\)，以及元素 \(h \in \mathbb{Z}_p^*\)，求整数 \(x\) 使得：
记作 \(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）正是从这类"陪集常值函数"中提取隐藏子群的标准工具。
算法步骤¶
第一步：量子叠加制备
制备两个寄存器的均匀叠加态：
（归一化是对的：\((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\)，将结果写入第三个寄存器：
关键性质：由 \(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\)，其解集为
（把每个 \(b\) 代入解出唯一的 \(a\)，共 \(n\) 个解。）这些解集是一个固定子群的平移：集合
对加法封闭（两个满足同余式的元素之和仍满足），是 \(\mathbb{Z}_n \times \mathbb{Z}_n\) 的子群，而解集恰为陪集 \(\Lambda + (r, 0)\)。\(f\) 在 \(\Lambda\) 的每个陪集上取常值、在不同陪集上取不同值——\(f\) 隐藏了子群 \(\Lambda\)，而 \(\Lambda\) 由 \(x\) 完全决定。
第三步：量子傅里叶变换（QFT）
对前两个寄存器施加二维 QFT：
随后测量前两个寄存器。测量结果 \((c, d)\) 以均匀概率满足线性关系（完整推导见下文"理论推导"一节）
于是当 \(c\) 与 \(n\) 互素时，一次解出 \(x \equiv c^{-1} d \pmod{n}\)。
第四步：经典后处理
从测量结果 \((c, d)\) 计算 \(x \equiv c^{-1} d \pmod{n}\)（用扩展欧几里得算法求 \(c^{-1}\)）
若 \(\gcd(c, n) > 1\)，将同余式两边除以 \(\gcd(c,n)\) 得到 \(x\) 模 \(n/\gcd(c,n)\) 的信息，多次测量收集多个方程后用中国剩余定理（Chinese Remainder Theorem, CRT）合并
理论推导¶
测量分布的完整推导¶
我们对第三步做完整计算。由关键性质，把 \(|\psi_1\rangle\) 按第三个寄存器的取值分组：
内层括号正是陪集 \(\Lambda + (r, 0)\) 上 \(n\) 个基态的均匀叠加。对前两个寄存器施加 \(\text{QFT}_n \otimes \text{QFT}_n\)，由线性性，基态 \(|c\rangle|d\rangle|g^r\rangle\) 的振幅为
其中我们把与 \(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\) 在 \(\mathbb{Z}_n\) 上均匀分布。
格结构分析¶
\(\mathbb{Z}_n \times \mathbb{Z}_n\) 中满足 \(a + xb \equiv 0 \pmod{n}\) 的点集 \(\Lambda\) 也可以看成 \(\mathbb{Z}^2\) 中的二维格（lattice），它的一组基为：
验证：\((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\) 得到合法的同余式
此时 \(\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【离散对数问题与密码学背景】（→ 问题定义）
基础：写出离散对数问题的输入与输出，并列出依赖其困难性的三类密码系统，各用一句话说明依赖方式。
基础：取 \(p = 19\)、\(g = 2\)、\(h = 7\)，逐一计算 \(2^1, 2^2, \ldots \pmod{19}\)，求出 \(x = \log_2 7\)。
进阶：设 \(g\) 是 \(\mathbb{Z}_p^*\) 的生成元，证明 \(g^u = g^v\) 当且仅当 \(u \equiv v \pmod{p-1}\)，并由此说明任意 \(h\) 的离散对数在模 \(p - 1\) 意义下存在且唯一。
提示：\(g\) 的阶恰为 \(p - 1\)，故 \(g^0, g^1, \ldots, g^{p-2}\) 互不相同且铺满整个群。
练习 2【隐藏子群归约】（→ 核心思想）
基础：由 \(h = g^x\) 推导 \(f(a, b) = g^a h^b = g^{a + xb \bmod n}\)，并计算 \(n = 12\)、\(x = 7\) 时 \((a, b) = (3, 5)\) 对应的指数 \(r\)。
进阶：解释"函数 \(f\) 隐藏子群 \(\Lambda\)"的两个条件——在每个陪集上取常值、在不同陪集上取不同值——为何同时成立，并说明求出 \(\Lambda\) 为何等价于求出 \(x\)。
提示：\(\Lambda\) 由方程 \(a + xb \equiv 0 \pmod{n}\) 定义，方程的系数正是待求的 \(x\)。
练习 3【算法四步流程】（→ 算法步骤）
基础：写出第一步制备的态 \(|\psi_0\rangle\)，说明振幅 \(\frac{1}{n}\) 为何保证归一化，并计算 \(p = 13\) 时前两个寄存器各需的量子比特数。
进阶：证明第二步的关键性质：对每个 \(r \in \mathbb{Z}_n\)，\(\{(a, b) : a + xb \equiv r \pmod{n}\} = \{(r - xb \bmod n,\, b) : b \in \mathbb{Z}_n\}\)，且该集合等于陪集 \(\Lambda + (r, 0)\)。
提示：先证 \(\Lambda\) 对加法封闭，再把 \((r, 0)\) 加到 \(\Lambda\) 的每个元素上验证同余式。
练习 4【测量分布的完整推导】（→ 测量分布的完整推导）
基础：设 \(\omega = e^{2\pi i/n}\) 且 \(\omega^k \neq 1\)，用等比数列求和证明 \(\sum_{b=0}^{n-1} \omega^{kb} = \frac{1 - \omega^{kn}}{1 - \omega^k} = 0\)。
进阶：复现正文的振幅计算：说明对 \(b\) 求和的几何级数何时等于 \(n\)、何时等于 \(0\)，并由此证明测得满足 \(xc \equiv d \pmod{n}\) 的 \((c, d)\) 的概率为 \(\frac{1}{n}\)、其余为 \(0\)，且全部概率之和为 \(1\)。
提示：满足条件的 \((c, d)\) 恰有 \(n\) 对——每个 \(c\) 唯一对应 \(d = xc \bmod n\)；对 \(r\) 求和时模长不变。
练习 5【格结构与对偶格】（→ 格结构分析）
基础：验证 \((n, 0)\) 与 \((-x, 1)\) 都满足 \(a + xb \equiv 0 \pmod{n}\)，并证明它们的任意整系数组合 \(m(n, 0) + l(-x, 1) = (mn - lx,\, l)\) 也满足该同余式。
进阶：证明测量结果集 \(\{(c,\, xc \bmod n) : c \in \mathbb{Z}_n\}\) 等于对偶格 \(\Lambda^* = \{(c, d) : ac + bd \equiv 0 \pmod{n},\ \forall (a, b) \in \Lambda\}\)。
提示：只需对基向量 \((n, 0)\) 与 \((-x, 1)\) 检验对偶条件：前者自动成立，后者化为 \(d \equiv xc \pmod{n}\)。
练习 6【成功概率与 CRT 后处理】（→ 成功概率与不可逆情形）
基础：对 \(n = 12\) 与 \(n = 10\) 分别计算 \(\phi(n)/n\)，并列出 \(n = 12\) 时使 \(c^{-1}\) 存在的全部 \(c\) 值。
进阶：设测得 \(g_0 = \gcd(c, n) > 1\)，证明 \(g_0 \mid d\)，推导约化同余式 \(c'x \equiv d' \pmod{n'}\)（\(c = g_0 c'\)、\(d = g_0 d'\)、\(n = g_0 n'\)），并证明 \(\gcd(c', n') = 1\)。
提示：把 \(d\) 写成 \((d - xc) + xc\)；若 \(\gcd(c', n') > 1\)，则与 \(g_0\) 是最大公约数矛盾。
练习 7【数值实例：p = 13】（→ 数值实例）
基础：不看正文表格，对测量结果 \((c, d) = (5, 11)\) 与 \((7, 1)\) 分别求 \(c^{-1} \bmod 12\) 并恢复 \(x\)，再用 \(2^x \bmod 13\) 验证。
进阶：某次测量得到 \((c, d) = (2, 2)\)：写出约化后的同余式并给出 \(x\) 的候选集；若第二次测量得到 \((c, d) = (3, 9)\)，用两次结果共同确定 \(x \bmod 12\)。
提示：两次测量分别给出 \(x\) 模 \(6\) 与模 \(4\) 的信息，而 \(\operatorname{lcm}(6, 4) = 12\)。
练习 8【对椭圆曲线的推广】（→ 对椭圆曲线的推广）
基础：写出 ECDLP 版本中模幂运算被替换后的酉变换 \(|a\rangle|b\rangle|0\rangle \to |a\rangle|b\rangle|aG + bH\rangle\)，并指出二维 QFT 改在哪个群的阶上进行。
进阶：对基点阶 \(n \approx 2^{256}\) 的 256 位曲线，分别估算经典 Pollard rho 与 Shor 算法的运算量级，并解释"指数加速"的含义。
提示：经典需 \(2^{128}\) 量级，是输入长度的指数函数；量子门数为 \((\log_2 n)^3 = 256^3\) 量级，只是多项式。
参考文献：
Shor, P. W. (1994). Algorithms for quantum computation: discrete logarithms and factoring. FOCS 1994.
Proos, J., & Zalka, C. (2003). Shor's discrete logarithm quantum algorithm for elliptic curves. Quantum Information & Computation, 3(4), 317-344.
NIST (2024). Post-Quantum Cryptography Standardization. https://csrc.nist.gov/projects/post-quantum-cryptography
Roetteler, M., Naehrig, M., Svore, K. M., & Lauter, K. (2017). Quantum resource estimates for computing elliptic curve discrete logarithms. ASIACRYPT 2017.
返回目录：量子计算算法教程系列