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)$ 满足：

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

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

第四步：经典后处理

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

代码示例（uniqc 实现）

类型：核心子程序演示 —— 用 uniqc 自建标准 QFT 完成 2D-QFT 求对偶格，模幂部分以 NumPy 矩阵编译。设 $p=17, g=3$，目标 $h=5$，群阶 $n=16=2^4$（恰好幂次方便 QFT），真实解 $x=5$。

import numpy as np
from uniqc import Circuit

P, G, H_TARGET = 17, 3, 5
N, M = P - 1, int(np.log2(P - 1))   # n = 16, m = 4

def build_qft(n: int) -> Circuit:
    """用 cp + swap 自建标准 QFT
（uniqc 0.0.15 的 qft_circuit 内部用 CRz 近似 CP，存在相位误差）"""
    c = Circuit()
    for j in range(n):
        c.h(j)
        for k in range(j + 1, n):
            c.cp(j, k, np.pi / (2 ** (k - j)))
    for i in range(n // 2):
        c.swap(i, n - 1 - i)
    return c

# 1. 编译模幂 f(a, b) = g^a · h^b mod p；测量工作寄存器得 y=1，
#    计数寄存器投影到格 Λ = {(a, b) : a + xb ≡ 0 (mod n)}
f_table = np.array([[(pow(G, a, P) * pow(H_TARGET, b, P)) % P
                     for b in range(N)] for a in range(N)])
mask = (f_table == 1)
psi = mask.astype(complex).flatten()
psi /= np.linalg.norm(psi)

# 2. 用 uniqc 的 QFT_16 ⊗ QFT_16 作用（uniqc 内部 little-endian → 标准索引置换）
perm = np.array([int(format(i, f'0{M}b')[::-1], 2) for i in range(2**M)])
P_perm = np.eye(2**M)[perm]
qft_std = P_perm @ build_qft(M).get_matrix() @ P_perm
final = np.kron(qft_std, qft_std) @ psi
probs = (np.abs(final) ** 2).reshape(N, N)

# 3. 对每个高概率 (c, d) 计算 x = d · c^(-1) mod n
print('   c |  d |    P    | gcd(c,n) | x = d · c^(-1)')
print('  ---+----+---------+----------+---------------')
for c in range(N):
    for d in range(N):
        if probs[c, d] < 1e-6:
            continue
        g_cn = int(np.gcd(c, N))
        if g_cn == 1:
            x_rec = (d * pow(c, -1, N)) % N
            tag = '★' if x_rec == 5 else ''
            print(f'{c:>2}|{d:>2}|{probs[c,d]:.5f}|{g_cn:>2}|{x_rec:>2}{tag}')
        else:
            print(f'{c:>2}|{d:>2}|{probs[c,d]:.5f}|{g_cn:>2}|    N/A')

运行结果（节选）：

■ 测量工作寄存器得 y = 1; 计数寄存器坍缩到格点 Λ:
  共 16 个 (a, b) 点; 验证 a + 5b ≡ 0 (mod 16) → True

■ 计数寄存器经 QFT ⊗ QFT 后的非零测量概率（共 16 个峰，均匀分布 P=1/16）:
   (c, d) | P=0.0625 | (d - cx) mod n
  ( 0, 0) ( 1, 5) ( 2,10) ( 3,15) ( 4, 4) ( 5, 9) ( 6,14) ( 7, 3)
  ( 8, 8) ( 9,13) (10, 2) (11, 7) (12,12) (13, 1) (14, 6) (15,11)
  ⇒ 全部 16 个峰都满足 d - 5c ≡ 0 (mod 16)，即落在对偶格 Λ* 上

■ 对每个 (c, d) 计算 x = d · c^(-1) (mod n):
   c |  d | gcd(c,n) | c^(-1) | x = d · c^(-1)
  ---+----+----------+--------+--------------
    1|  5 |     1    |    1   |      5  ★
    3| 15 |     1    |   11   |      5  ★
    5|  9 |     1    |   13   |      5  ★
    7|  3 |     1    |    7   |      5  ★
    9| 13 |     1    |    9   |      5  ★
   11|  7 |     1    |    3   |      5  ★
   13|  1 |     1    |    5   |      5  ★
   15| 11 |     1    |   15   |      5  ★

■ 单次测量直接恢复正确 x = 5 的概率: 0.5000
   (其余结果或 c 不可逆，或 c=0 无信息)

观察：

1. 模幂阶段把”$x$ 隐藏在 $a+xb$ 中”这一周期性信息埋入计数寄存器；测量工作寄存器投影到二维格 $\Lambda$ 上 16 个等幅点
2. 二维 QFT 把 $\Lambda$ 上的均匀叠加变换为对偶格 $\Lambda^*=\{(c,d):d\equiv cx \pmod n\}$ 上的均匀分布，16 个峰每个 $P=1/16$
3. 单次测量直接成功率 = $\phi(n)/n = \phi(16)/16 = 8/16 = 0.5$（与理论一致）；其余 $c$ 与 $n$ 不互素时需重测或用中国剩余定理合并
4. 若选择更大的 $p$（如 $p=2^k+1$ 的费马素数），$n$ 仍是 2 的幂，所有 $c$ 奇数都给出唯一解，单次成功率仍是 $1/2$

理论推导

格结构分析

$\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^*$ 的一个元素：

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

成功概率

单次测量得到 $\gcd(c, n) = 1$（从而可直接计算 $x$）的概率为 $\phi(n)/n$，其中 $\phi$ 为欧拉函数。当 $n$ 的素因子较少时，$\phi(n)/n$ 较大。

若 $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.

返回目录：量子计算算法教程系列