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

问题定义

离散对数问题

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

$$g^x \equiv h \pmod{p}$$

记作 $x = \log_g h$。

为什么重要

• Diffie-Hellman 密钥交换：双方共享 $g^{ab} \bmod p$，安全性基于计算 $g^{ab}$ 从 $g^a, g^b$ 的困难性
• DSA 数字签名：签名验证依赖 DLP 的困难性
• 椭圆曲线密码（ECC）：椭圆曲线离散对数问题（ECDLP），目前没有经典亚指数算法

经典最优算法：

• 一般 DLP：指数时间 $O(e^{O(\sqrt{\log p \log\log p})})$（数域筛法）
• ECDLP：$O(\sqrt{p})$（Pollard rho 算法），对 256 位曲线 $O(2^{128})$

Shor 算法求解离散对数

核心思想

Shor 的 DLP 算法将离散对数 $x = \log_g h$ 归约为隐藏子群问题（Hidden Subgroup Problem）：找到函数 $f(a, b) = g^a h^b \bmod p$ 的周期。

算法步骤

第一步：量子叠加制备

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

$$|\psi_0\rangle = \frac{1}{p-1} \sum_{a=0}^{p-2} \sum_{b=0}^{p-2} |a\rangle|b\rangle|0\rangle$$

每个寄存器有 $\lceil\log_2(p-1)\rceil$ 个量子比特。

第二步：模幂计算

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

$$|\psi_1\rangle = \frac{1}{p-1} \sum_{a,b} |a\rangle|b\rangle|g^a h^b \bmod p\rangle$$

关键性质：$g^a h^b = g^a \cdot g^{xb} = g^{a + xb}$，因此 $g^a h^b \bmod p$ 仅依赖于 $(a + xb) \bmod (p-1)$。

令 $n = p - 1$（群的阶）。对每个 $r \in \mathbb{Z}_n$，$f(a,b) = g^r$ 当且仅当 $a + xb \equiv r \pmod{n}$。解为 $(a, b) = (r + kt, -k) \bmod n$（$k = 0, 1, \ldots, n-1$），其中 $t$ 满足某些条件。

实际上，集合 $\{(a, b) : a + xb \equiv 0 \pmod{n}\}$ 构成 $\mathbb{Z}_n \times \mathbb{Z}_n$ 的一个格（lattice），其基向量与 $x$ 直接相关。

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

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

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

测量后，$(c, d)$ 满足：

$$cx + d \equiv 0 \pmod{n}$$

即 $cx \equiv -d \pmod{n}$，从而 $x \equiv -d c^{-1} \pmod{n}$（若 $c$ 在模 $n$ 下可逆）。

第四步：经典后处理

1. 从测量结果 $(c, d)$ 计算 $x \equiv -d \cdot c^{-1} \pmod{n}$
2. 若 $\gcd(c, n) > 1$，重复测量直到 $c$ 与 $n$ 互素

理论推导

格结构分析

$\mathbb{Z}_n \times \mathbb{Z}_n$ 中满足 $a + xb \equiv 0 \pmod{n}$ 的点集 $\Lambda$ 是一个二维格。其基为：

$$\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}$ ✓

QFT 测量结果 $(c, d)$ 是 $\Lambda$ 的对偶格 $\Lambda^*$ 的一个元素：

$$cx + d \equiv 0 \pmod{n}$$

成功概率

单次测量得到 $\gcd(c, n) = 1$（从而可直接计算 $x$）的概率为 $\phi(n)/n$，其中 $\phi$ 为欧拉函数。对素数 $n = p-1$，概率 $\approx 1$。

若 $n$ 有小素因子，可用中国剩余定理分别求解各模分量，再合并。

对椭圆曲线的推广

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})$ 相比为指数加速。

与整数分解的关系

定理：整数分解可以在多项式时间内归约为离散对数问题。

构造：给定 $N = pq$，选 $a$ 随机，$\gcd(a, N) = 1$。计算 $a^{N-1} \bmod N$ 的阶 $r$（即 $a^r \equiv 1 \pmod{N}$）就是 DLP 的特例（$h = 1$）。

因此：DLP 的量子算法自动给出整数分解的量子算法。

逆向：反之不成立——DLP 一般不归约为整数分解。DLP 是更难的问题。

对密码学的影响

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

复杂度分析

对比经典：

总结

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.