# 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.
---

> 返回目录：[量子计算算法教程系列](https://chenzhaoyun.com/index.php/archives/54/)