离散对数的量子算法

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

问题定义

离散对数问题

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

$g^x\equiv h(\mathrm{mod}p)$

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

为什么重要

• Diffie-Hellman 密钥交换：双方公开 $g^a$ 与 $g^b$，共享密钥为 $g^{ab}\mathrm{mod}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\mathrm{mod}p$。由 $h=g^x$ 可知 $f(a,b)=g^{a+xb\mathrm{mod}n}$，它在一个二维格的每个陪集上取常值、在不同陪集上取不同值；求出这个隐藏的格，等价于求出 $x$。量子傅里叶变换（QFT）正是从这类”陪集常值函数”中提取隐藏子群的标准工具。

算法步骤

第一步：量子叠加制备

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

$|{\psi }_0⟩=\frac{1}{n}{\sum }_{a=0}^{n-1}{\sum }_{b=0}^{n-1}|a⟩|b⟩|0⟩$

（归一化是对的：$(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\mathrm{mod}p$，将结果写入第三个寄存器：

$|{\psi }_1⟩=\frac{1}{n}{\sum }_{a,b}|a⟩|b⟩|g^a{h}^b\mathrm{mod}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(\mathrm{mod}n)$。于是 $f(a,b)$ 只依赖于 $(a+xb)\mathrm{mod}n$：对每个 $r\in {\mathbb{Z}}_n$，$f(a,b)=g^r$ 当且仅当 $a+xb\equiv r(\mathrm{mod}n)$，其解集为

$\{(a,b):a+xb\equiv r(\mathrm{mod}n)\}=\{(r-xb\mathrm{mod}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(\mathrm{mod}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⟩|b⟩\to \frac{1}{n}{\sum }_{c=0}^{n-1}{\sum }_{d=0}^{n-1}{e}^{2\pi i(ac+bd)/n}|c⟩|d⟩$

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

$xc\equiv d(\mathrm{mod}n)$

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

第四步：经典后处理

1. 从测量结果 $(c,d)$ 计算 $x\equiv c^{-1}d(\mathrm{mod}n)$（用扩展欧几里得算法求 $c^{-1}$）
2. 若 $\gcd (c,n)>1$，将同余式两边除以 $\gcd (c,n)$ 得到 $x$ 模 $n/\gcd (c,n)$ 的信息，多次测量收集多个方程后用中国剩余定理（Chinese Remainder Theorem, CRT）合并

理论推导

测量分布的完整推导

我们对第三步做完整计算。由关键性质，把 $|{\psi }_1⟩$ 按第三个寄存器的取值分组：

$|{\psi }_1⟩=\frac{1}{n}{\sum }_{r\in {\mathbb{Z}}_n}\left({\sum }_{b\in {\mathbb{Z}}_n}|(r-xb)\mathrm{mod}n⟩|b⟩\right)|g^r⟩$

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

${\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 irc/n}}{n^2}{\sum }_{b\in {\mathbb{Z}}_n}{\left(e^{2\pi i(d-xc)/n}\right)}^b$

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

• 若 $d\equiv xc(\mathrm{mod}n)$，每项都是 1，级数等于 $n$；
• 若 $d\not\equiv xc(\mathrm{mod}n)$，则 $e^{2\pi i(d-xc)/n}\ne 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(\mathrm{mod}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\mathrm{mod}n$），概率总和为 1。结论：

$(c,d)\text{ 均匀分布于 }\{(c,xc\mathrm{mod}n):c\in {\mathbb{Z}}_n\}，\text{恒有 }xc\equiv d(\mathrm{mod}n)$

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

格结构分析

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

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

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

上一节的测量结果集 $\{(c,xc\mathrm{mod}n)\}$ 恰是 $\Lambda$ 的（模 $n$ 意义下的）对偶格（dual lattice）${\Lambda }^{\ast }=\{(c,d):ac+bd\equiv 0(\mathrm{mod}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$）的概率为 $\varphi (n)/n$，其中 $\varphi$ 为欧拉函数（Euler’s totient function）。注意 $n=p-1$ 是偶数（$p$ 为奇素数），必然是合数，因此 $\varphi (n)/n={\prod }_{\ell \mid n}\left(1-\frac{1}{\ell }\right)$ 严格小于 1；例如 $n=12=2^2\cdot 3$ 时 $\varphi (12)/12=\frac{1}{2}\cdot \frac{2}{3}=\frac{1}{3}$。

若测得 $g_0=\gcd (c,n)>1$，也不必丢弃这次结果。同余式 $xc\equiv d(\mathrm{mod}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}^{\prime }$、$n=g_0{n}^{\prime }$、$d=g_0{d}^{\prime }$，同余式两边除以 $g_0$ 得到合法的同余式

$c^{\prime }x\equiv d^{\prime }(\mathrm{mod}{n}^{\prime }),d^{\prime }=d/g_0,n^{\prime }=n/g_0$

此时 $\gcd (c^{\prime },n^{\prime })=1$，解得 $x\mathrm{mod}{n}^{\prime }$。多次测量得到 $x$ 模 $n$ 的各个”分量”后，用中国剩余定理合并即可恢复 $x\mathrm{mod}n$。

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

取 $p=13$，则 $n=12$。$2$ 是 ${\mathbb{Z}}_{13}^{\ast }$ 的生成元（逐一计算 $2^1,2^2,\dots ,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(\mathrm{mod}13)$。

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

测得 $c$	对应 $d=7c\mathrm{mod}12$	$\gcd (c,12)$	后处理
1	7	1	$x\equiv 1^{-1}\cdot 7=7(\mathrm{mod}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(\mathrm{mod}6)$，即 $x\in \{1,7\}$，需再测一次合并

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

对椭圆曲线的推广

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

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

量子电路修改：

• 模幂运算替换为椭圆曲线点乘：$|a⟩|b⟩|0⟩\to |a⟩|b⟩|aG+bH⟩$
• QFT 在椭圆曲线群的阶 $n$ 上进行
• 其余步骤完全相同

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

与整数分解的关系

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

一方面，整数分解被归约为一维周期查找：给定 $a$ 与 $N$，函数 $x\mapsto a^x\mathrm{mod}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.

---

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch04-classic-algorithms/shors-discrete-log-tutorial
• 内容遵循 CC BY-NC-SA 4.0 许可协议