椭圆曲线离散对数的空间高效量子算法

本文基于 Han Luo, Ziyi Yang, Jingquan Luo, Ziruo Wang, Yuexin Su, Xiaoming Sun, Lvzhou Li, Tongyang Li 等人 2026 年论文《Quantum Algorithm for Elliptic Curve Discrete Logarithms with Space-Efficient Point Addition》整理。原稿篇幅较长，涵盖量子线路构造、可逆模逆电路、仿射点加、资源估计等多个技术细节。本文聚焦于算法的核心思想与数学框架，对量子线路的具体构造做精简介绍，力求以清晰的中文讲解呈现这一空间高效算法的完整脉络。

1. 引言：椭圆曲线密码学与量子威胁

1.1 椭圆曲线密码学

椭圆曲线密码学（Elliptic Curve Cryptography, ECC）由 Koblitz（1987）与 Miller（1985）分别独立提出，是现代公钥密码学的基础原语之一。其安全性建立在椭圆曲线离散对数问题（ECDLP）的计算困难性之上。

设 (p) 为大素数，(\mathbb{F}_p) 为含 (p) 个元素的有限域。一条短 Weierstrass 形式的椭圆曲线 (E/\mathbb{F}_p) 定义为仿射解集 ((x, y) \in \mathbb{F}_p^2) 满足

$$
y^2 = x^3 + ax + b,
$$

加上一个无穷远点 (\mathcal{O})。曲线上的 (\mathbb{F}_p)-有理点构成一个 Abel 群，群运算为椭圆曲线加法。

对于仿射点 (P_1 = (x_1, y_1)) 与 (P_2 = (x_2, y_2))（互不为逆元），其和 (P_3 = P_1 + P_2) 通过斜率参数 (\lambda) 计算：

$$
x_3 = \lambda^2 - x_1 - x_2, \qquad y_3 = \lambda(x_1 - x_3) - y_1,
$$

其中当 (P_1 \neq P_2) 时 (\lambda = \frac{y_2 - y_1}{x_2 - x_1})（弦斜率），当 (P_1 = P_2) 时 (\lambda = \frac{3x_1^2 + a}{2y_1})（切线斜率）。

标量乘法 (m \mapsto [m]P) 是 ECC 的核心原语，其中 ([m]P = P + P + \cdots + P)（(m) 次）。

1.2 椭圆曲线离散对数问题

设 (P \in E(\mathbb{F}_p)) 生成一个阶为 (r) 的循环子群 (\langle P \rangle)，给定 (Q \in \langle P \rangle)，ECDLP 要求恢复唯一的整数 (m \in {0, 1, \ldots, r-1}) 使得

$$
Q = [m]P.
$$

在经典计算机上，最优的通用算法（如 Pollard rho 方法）需要 (\Theta(\sqrt{p})) 次群运算——关于比特长度 (n = \lfloor \log_2 p \rfloor + 1) 是指数时间的。

ECC 相比 RSA 等传统公钥系统的优势在于：更短的密钥即可达到同等安全级别。例如，NIST 推荐的 256 位椭圆曲线提供 128 位安全级别，而 RSA 需要 3072 位模数。ECC 被广泛应用于 TLS、SSH、比特币等协议中。

1.3 量子计算的威胁

1994 年，Shor 给出了整数分解与离散对数的多项式时间量子算法。由于 ECDLP 本质上是椭圆曲线群中的离散对数问题，只要能高效实现椭圆曲线群运算，Shor 算法就可以直接应用于 ECDLP。

Proos 与 Zalka（2003）随后给出了素域椭圆曲线的量子资源分析。然而，在近期中量子硬件上实际运行 Shor 算法仍受到严重限制——需要大量逻辑量子比特和低错误率。

因此，降低量子算法的资源需求成为核心研究目标。本文的工作正是在这一方向上取得了重要突破。

2. Shor 算法在椭圆曲线上的实现

2.1 算法框架

Shor 的 ECDLP 量子算法使用两个指数寄存器和一个存储椭圆曲线点的寄存器。设 (n = \lfloor \log_2 p \rfloor + 1) 为 (p) 的比特长度。

  1. 初始化两个 ((n+1)) 量子比特寄存器为 (|0^{n+1}, 0^{n+1}\rangle)，对所有量子比特施加 Hadamard 门，得到均匀叠加态。

  2. 相干地计算椭圆曲线群作用：

$$
\sum_{k,\ell=0}^{2^{n+1}-1} |k, \ell\rangle |\mathcal{O}\rangle \mapsto \sum_{k,\ell=0}^{2^{n+1}-1} |k, \ell\rangle |[k]P + [\ell]Q\rangle.
$$

  1. 对两个指数寄存器施加量子傅里叶变换（QFT），然后测量。

  2. 经典后处理利用测量结果以高概率恢复离散对数 (m)。

2.2 半经典傅里叶变换

为减少与 QFT 相关的量子比特开销，可以用半经典傅里叶变换替代标准 QFT。半经典版本在计算过程中进行测量，重用量子比特，并根据先前观测结果施加条件相位旋转。这样指数寄存器仅需单个量子比特，节省了 (2n+1) 个量子比特。

2.3 资源瓶颈

算法的主要代价来自相干群求值——即椭圆曲线点的双标量乘法。每次受控点加可分解为一系列可逆模运算：模加、模乘、模平方和模除。其中，模逆运算是逻辑量子比特消耗的最大来源。

因此，降低模逆电路的空间复杂度是降低整体资源需求的关键。

3. 空间高效的扩展欧几里得算法

3.1 经典扩展欧几里得算法

设 (p > x) 为两个正整数。扩展欧几里得算法（EEA）不仅计算 (\gcd(p, x))，还在 (p, x) 互素时输出模逆 (x^{-1} \bmod p)。

算法初始化 (r_0 := p, r_1 := x)，以及 (t_0 := 0, t_1 := 1)。在第 (i) 次迭代中：

  1. 计算商 (q_i = \lfloor r_{i-1}/r_i \rfloor)。
  2. 更新余数 (r_{i+1} = r_{i-1} - q_i r_i)。
  3. 更新辅助变量 (t_{i+1} = t_{i-1} + q_i t_i)。

当首次遇到 (r_k = 1) 时，模逆为 ((-1)^{k-1} t_k \bmod p)。

3.2 量子实现的挑战

在量子计算机上实现 EEA 时，主要困难在于输入 (x) 可能处于叠加态。不同输入所需的迭代次数从 1 到 (O(n)) 不等，直接实现需要 (O(n)) 次迭代，每次涉及 (n) 位数的除法和乘法，总门复杂度为 (O(n^3))。

3.3 四阶段算法框架

Proos 与 Zalka（2003）提出了适合量子实现的四阶段算法框架。每次 EEA 迭代被分解为四个阶段：

  • 阶段 1：将 (r_i) 反复左移一位，同时递增移位计数器 (\ell)，直到 (2^\ell r_i > r_{i-1})。确定 (q_i) 二进制表示中的最高位位置。

  • 阶段 2：将 (r_i) 逐步右移，同时递减 (\ell)。在每一步根据条件更新 (r_{i-1}) 和部分商 (q')，最终完成 (q_i = \lfloor r_{i-1}/r_i \rfloor) 的计算。

  • 阶段 3：将 (t_i) 逐步左移，同时递增 (\ell)。根据 (q_i) 的各位值更新 (t_{i-1})，完成 (t_{i-1} \leftarrow t_{i-1} + q_i t_i) 的更新。

  • 阶段 4：将 (t_i) 逐步右移，递减 (\ell)，直到 (\ell = 0)。

四个阶段完成后，对 ((r_{i-1}, r_i)) 和 ((t_{i-1}, t_i)) 分别施加 SWAP 操作，完成一次 EEA 迭代。

3.4 步数的严格上界

一个关键性质是：完成整个 EEA 所需的总步数 (N) 被严格限制在

$$
4n \le N \le 4\lceil cn \rceil,
$$

其中 (c = 3/\log_2(2+\sqrt{3}) \approx 1.579)。

这意味着对于任意叠加态输入，量子电路只需重复固定次数 (4\lceil cn \rceil < 6.316n) 步即可确定性地得到模逆。由于每步涉及 (O(n)) 个量子门，总门复杂度降为 (O(n^2))。

4. 寄存器共享技术

4.1 核心思想

本文的核心创新在于对 Proos-Zalka 寄存器共享策略的精化。

在 EEA 执行过程中，序列 ({r_i}) 单调递减，而 ({t_i}) 单调递增。这种互补行为允许两者在不同计算阶段共享同一个量子寄存器。由恒等式

$$
r_{i-1} t_i + r_i t_{i-1} = p,
$$

可知两个 ((n+2)) 量子比特的寄存器就足以存储所需的中间变量。

4.2 寄存器分配

本文进一步将寄存器共享推向极致，用单个 ((n+3)) 量子比特寄存器同时存储三元组 ((r, t, q)) 的中间状态：

  • Work1 寄存器（(n+3) 量子比特）：左侧 (\ell_t + 1) 位存储 (t = t_i)（小端序），中间 (\ell_q) 位存储部分商 (q')（大端序），其余位存储 (r = r_{i-1})（大端序）。

  • Work2 寄存器（(n+3) 量子比特）：右侧 (\ell_{r'}) 位存储 (r' = r_i)（大端序），其余位存储 (t' = t_{i-1})（小端序）。

  • 长度寄存器：四个辅助寄存器 (\ell_t, \ell_q, \ell_{r'}, \ell_s)，各含 (\lfloor \log_2 n \rfloor + 1) 量子比特，标记 Work 寄存器中的逻辑边界。

  • 控制寄存器：Phase1, Phase2（指示当前阶段）、Iter（迭代奇偶性）、Sign（中间标志位）。

4.3 精确分配方案

原 Proos-Zalka 构造使用统一寄存器分配来适应所有输入 (x \in \mathbb{F}_p) 的叠加，这种最坏情况分配引入 (O(\sqrt{n})) 的空间开销，且需要截断罕见的异常情形，导致 (O(n^{-2})) 的保真度损失。

本文给出了精确分配方案：对所有输入 (x \in \mathbb{F}_p) 保证确定性的寄存器界，额外空间开销仅为 (O(\log n))，同时保持精确正确性。

5. 模逆电路的量子构造

5.1 位置受控运算

模逆电路的关键非标准组件是位置受控运算（location-controlled operations）——根据长度寄存器的值，在 Work 寄存器的特定位置施加算术运算。

主要包括：

  • 位置受控 SWAP：将 Sign 量子比特与 Work1 的第 ((\ell_t + \ell_q + 1)) 位交换。
  • 位置受控加/减：在 Work1 和 Work2 的特定区间 ([L, R]) 上执行模加或模减。
  • 长度更新电路：在 EEA 迭代结束时更新 (\ell_t) 和 (\ell_{r'})。

5.2 单步迭代实现

利用一元迭代（unary iteration）原语实现位置受控运算。对于已知区间 ([k, K])，一元迭代可视为一棵二叉树，叶节点为区间中的标签。每个内部节点存储标签子集，通过可逆 AND 门逐步选择目标位置。

一元迭代的代价为 (K - k + O(1)) 个 Toffoli 门和 (O(\log_2(K-k))) 个临时控制量子比特，远优于独立等值测试的 (O(M \log_2 n)) 个 Toffoli 门。

5.3 步依赖活跃窗

为降低门复杂度，本文引入了步依赖活跃窗（step-dependent active windows）。在每一步 (T)，位置受控运算的作用区间被限制在已知的上下界 ([k(T), K(T)]) 之内，避免对不可能被激活的位置施加运算。

例如，对 (r) 的位置受控加/减，其活跃窗的上界为 (K_1(T) = n + 3)，下界为

$$
k_1(T) = \max\left{\left\lceil \frac{T - n - 1 - 4\delta}{4c - 1} \right\rceil, 1 + 2\right},
$$

其中 (\delta \approx 0.726)。

5.4 资源统计

综合所有贡献，模逆电路的总资源为：

  • 空间：(2n + 6\lfloor \log_2 n \rfloor + 19) 个逻辑量子比特
  • Toffoli 门：(229n^2 + O(n \log^2 n)) 个
  • CNOT 门：(286n^2 + O(n \log^2 n)) 个

6. 基于中间测量的仿射点加

6.1 问题描述

仿射点加需要执行原地除法：

$$
|x\rangle_X |y\rangle_Y |0\rangle_A \mapsto |x\rangle_X |y/x\rangle_Y |0\rangle_A.
$$

直接实现这一映射的困难在于：先对 (x) 运行正向 EEA 求逆电路（使用 (A) 作为工作空间），将商 (y/x) 写入 (A) 后，(A) 不再"干净"，无法作为逆向 EEA 电路的工作空间来清除中间状态。

6.2 中间测量解决方案

本文的巧妙解决方案是中间测量与经典前馈：

  1. 对 (X) 运行正向 EEA 求逆电路，使用 (A) 作为大工作空间：

$$
|x\rangle_X |y\rangle_Y |0\rangle_A |0\rangle_S \mapsto |x^{-1}\rangle_X |y\rangle_Y |0\rangle_A |\Gamma(x)\rangle_S.
$$

  1. 用标准模乘将商写入 (A)：(|x^{-1}\rangle_X |y\rangle_Y |0\rangle_A \mapsto |x^{-1}\rangle_X |y\rangle_Y |y/x\rangle_A)。

  2. 对 (Y) 施加 (H^{\otimes n}) 并在计算基下测量。若经典结果为 (b \in {0,1}^n)，剩余量子态获得相位 ((-1)^{b \cdot y})。(Y) 被重置为 (|0\rangle)。

  3. 现在 (Y) 是干净的 (n) 量子比特寄存器，可用作逆向 EEA 电路的工作空间：

$$
(-1)^{b \cdot y} |x^{-1}\rangle_X |0\rangle_Y |y/x\rangle_A |\Gamma(x)\rangle_S \mapsto (-1)^{b \cdot y} |x\rangle_X |0\rangle_Y |y/x\rangle_A |0\rangle_S.
$$

  1. 从 (x) 和 (y/x) 重新计算 (y)，施加 Pauli (Z) 校正消除测量相位，再撤销重新计算。

  2. 交换 (Y) 和 (A)，完成原地除法。

6.3 正确性分析

测量 (|y\rangle) 在 Hadamard 基下给出均匀随机的结果 (b)，对剩余寄存器的唯一影响是相位 ((-1)^{b \cdot y})。由于相位可以通过重新计算和经典前馈消除，测量不破坏相干性。

这一技术使得仿射点加仅需三个 (n) 量子比特场寄存器 (X, Y, A)，加上 EEA 电路所需的 (O(\log_2 n)) 个辅助量子比特。

7. 资源估计总结

7.1 空间复杂度

组件 逻辑量子比特数
模逆电路 (2n + 6\lfloor \log_2 n \rfloor + 19)
仿射点加 (3n + 6\lfloor \log_2 n \rfloor + 19)

7.2 门复杂度

组件 Toffoli 门数
模逆电路 (229n^2 + O(n \log^2 n))
单次仿射点加 (1051n^2 + O(n \log^2 n))
完整 ECDLP 算法 (1056n^3 / \log_2 n + O(n^2))

完整 ECDLP 算法使用符号窗技术（signed-window technique）将控制位分为大小为 (w = 2\log_2 n) 的窗，每窗通过一次受控仿射点加和查表实现。

7.3 secp256k1 的具体资源

对于广泛使用的 secp256k1 曲线（(n = 256)）：

指标 本工作 此前最优
逻辑量子比特 835 1098 [CFS26]
Toffoli 门 (2^{30.88}) (2^{38.10}) [CFS26]

相比此前最优的空间优化估计（Chevignard et al. 2026），节省了超过 250 个逻辑量子比特，同时 Toffoli 门数降低了两个数量级。

8. 与已有工作的比较

本文在三个核心资源指标上的定位：

  • 空间复杂度：达到目前报道的最佳渐近逻辑量子比特复杂度 (3n + O(\log n))，优于 Chevignard et al. 的 (3.12n + o(n))。

  • 门复杂度：(O(n^3/\log n)) 的 Toffoli 门数显著优于 Chevignard et al. 的 (O(n^4))，尽管略逊于以门数为优化目标的工作。

  • 电路深度：本文未做详细分析，这是未来工作的重要方向。

本文的独特优势在于：所有算术组件都给出了精确的可逆电路构造，而非高层抽象分析，使得资源估计具有严格的可复现性。

9. 开放问题

本文留下了几个值得进一步研究的方向：

  1. 门数优化：位置受控算术、长度寄存器更新、受控模运算等构建块的门数可能仍有改进空间。

  2. 深度分析与空间-深度权衡：研究模逆和点加电路的深度，识别可并行化的部分，量化空间、门数与深度之间的权衡。

  3. 超越椭圆曲线离散对数的应用：模逆是通用算术原语，本文发展的空间高效可逆 EEA 和寄存器共享技术可能改善其他需要模除或模逆的量子算法。

  4. AI 辅助量子算术电路发现：探索 AI 系统能否自动化设计量子算术电路，支持新电路的发现和现有电路的优化。

参考文献

[1] Luo H, Yang Z, Luo J, et al. Quantum Algorithm for Elliptic Curve Discrete Logarithms with Space-Efficient Point Addition[J]. arXiv:2607.13816v3 [quant-ph], 2026.

[2] Shor P W. Algorithms for quantum computation: Discrete logarithms and factoring[C]// Proceedings of the 35th Annual Symposium on Foundations of Computer Science. IEEE, 1994: 124–134.

[3] Proos J, Zalka C. Shor's discrete logarithm quantum algorithm for elliptic curves[J]. Quantum Information & Computation, 2003, 3(4): 317–344.

[4] Häner T, Jaques S, Naehrig M, et al. Improved quantum circuits for elliptic curve discrete logarithms[C]// International Conference on Post-quantum Cryptography. Springer, 2020: 425–444.

[5] Chevignard C, Fouque P A, Schrottenloher A. Reducing the number of qubits in quantum discrete logarithms on elliptic curves[R]. Cryptology ePrint Archive, Paper 2026/280, 2026.

[6] Roetteler M, Naehrig M, Svore K M, et al. Quantum resource estimates for computing elliptic curve discrete logarithms[C]// International Conference on the Theory and Application of Cryptology and Information Security. Springer, 2017: 241–270.