Shor 算法用于 ECDLP — Q-Day Prize 参赛作品

为 Q-Day Prize 挑战赛 构建的椭圆曲线离散对数问题（ECDLP）量子求解器，由 Project Eleven 开发。目标：在实际量子硬件上使用 Shor 算法恢复 ECC 私钥。

• 作者：Giancarlo Lelli
• 联系方式：[email protected]
• LinkedIn：https://www.linkedin.com/in/giancarlolelli
• 背景：技术领导者，拥有 10 年以上企业软件、全栈架构和云原生开发经验。计算机科学背景，熟练掌握 .NET、Python、Rust 和云生态系统。目前担任 Cloud GTM 专家，专注于解决方案架构和销售工程。

方法

所有挑战曲线的方程均为 y^2 = x^3 + 7 定义在 F_p 上（a = 0, b = 7），与 secp256k1 曲线族一致。该求解器实现了 Shor 算法用于 ECDLP 的双寄存器变体：

1. 准备计数寄存器 |j>、|k> 处于均匀叠加态（Hadamard 门）
2. 通过 2t 个受控点加法（t = 计数量子比特数）计算 |j>|k>|jG + kQ>
3. 测量点寄存器，使其坍缩为某个群元素 R
4. 对计数寄存器应用逆 QFT
5. 测量 j、k，并从关系式 j + kd = r (mod n) 中提取 d

私钥 d 通过收集多个满足相同线性关系（模群阶 n）的 (j, k) 样本来恢复。求解器支持六种用于受控点加法的预言机策略，系统会根据曲线大小自动选择，或通过 --oracle 手动指定。

预言机策略

策略 1：密集酉矩阵（默认用于 n_bits <= 6）

用于群阶不超过约 6 比特的曲线。在 projecteleven.py 中实现。

每个受控点加法 "add S" 表示为一个 2^(n+1) x 2^(n+1) 的置换矩阵，通过 qc.unitary() 应用。该矩阵编码了完整的群作用：左上角分块是恒等变换（控制位=0），右下角分块根据映射 P -> P+S（控制位=1）对基态进行置换。

• 编码：群索引 (0..n-1)
• 内存：每个矩阵 O(2^{2n})
• 量子比特：2t + n（两个计数寄存器 + 点寄存器）
• 限制：Qiskit 的酉矩阵分解复杂度为 O(4^n)，使得该策略在超过约 6 比特时不可行

策略 2：高效置换分解（默认用于 n_bits > 6）

用于较大曲线。在 quantum_arithmetic.py 中实现。

不构建密集矩阵，而是将每个 "add S" 置换分解为对换的循环。每个对换（两个基态 |a> <-> |b> 的交换）通过以下方式实现：

1. CNOT 约简——从枢轴比特到所有其他不同比特的 CNOT，将多位差异减少为单比特差异
2. 多控 X 门——作用于枢轴比特的 MCX 门，以所有其他比特与目标模式匹配为条件
3. 撤销 CNOT——逆步骤 1 以恢复非枢轴比特

MCX 使用 V 链分解，需要 (n-2) 个专用辅助量子比特，使得每个 MCX 的 Toffoli 门数量为 O(n)，而非无辅助量子比特时的 O(n^2)。每个受控加法构建为一个独立的子电路，并作为一个单独的不透明门附加，避免了 Qiskit 中 DAG 的二次增长。

• 编码：群索引 (0..n-1)
• 内存：每次加法 O(N)（N 为群阶）
• 量子比特：2t + n + (n-2) 个辅助量子比特
• 每次加法门数：O(N * n)

策略 3：基于坐标的量子预言机（--oracle coordinate）

适用于约 6 比特以下的曲线。在 quantum_oracle.py 中实现。

量子寄存器不将点编码为群索引，而是保存实际的 (x, y) 域元素坐标的二进制表示，再加上一个无穷远点标志。点寄存器布局为：

• x_reg：f_bits 个量子比特（f_bits = ceil(log2(p))）
• y_reg：f_bits 个量子比特
• id_flag：1 个量子比特（1 = 无穷远点）

每个受控 "add S" 根据对所有有效坐标编码的椭圆曲线加法公式计算，产生坐标寄存器上的一个置换。该置换使用与策略 2 相同的 CNOT 约简 + MCX 基础设施分解为对换的循环。

• 编码：(x, y, id_flag) 坐标
• 量子比特：2t + 2f_bits + 1 + max(0, 2f_bits - 1) 个辅助量子比特
• 每次加法门数：O(N * f_bits)

策略 4：算术预言机（--oracle arithmetic）

用于多项式缩放点加法的框架。在 quantum_oracle.py 和 quantum_arithmetic.py 中实现。

使用坐标编码（与策略 3 相同），并采用基于 QFT 的模算术原语作为构建块，旨在实现全算术点加法。代码库包含经过测试的实现：

• Beauregard 模加法器——基于 QFT 的（目标 + 常数）模 p，具有正确的辅助量子比特反计算
• 量子-量子模乘法——|a>|b>|0> -> |a>|b>|a*b mod p>，通过移位相加和显式模加倍实现，O(n^3) 门
• 模逆置换——|x> -> |x^{-1} mod p>，通过查找表对换实现
• 受控量子-量子模加法——受控 |a> -> |a + b mod p>，使用 Beauregard 约简

算术原语实现的每次加法缩放为 O(n^3)，而置换方法为 O(N*n)。然而，基于 QFT 的操作具有约 150 倍较大的常数因子，使得算术方法仅在曲线群阶超过约 20 比特时才更高效。对于当前挑战规模（最多 12 比特），基于置换的加法器仍然更快，因此默认使用。

策略 5：Google 半经典相位估计（--oracle google）

在 google_semiclassical.py 中实现。灵感来自 Griffiths & Niu (1996) 的量子比特回收相位估计技术，Babbush 等人 (2026) 将其应用于 secp256k1 ECDLP 资源估算中。Babbush 等人的论文发表于 2026 年 3 月 30 日。

将两个多量子比特计数寄存器（j、k）和批量逆 QFT 替换为两个单循环量子比特以及经典条件相位校正。每个计数寄存器比特按顺序处理：制备为 |+> 态，应用受控点加法，根据所有先前测量的比特校正相位，然后测量。reset 和 if_test 动态电路原语使这能在 IBM Quantum 硬件上实现。

受控点加法的预言机委托给现有基础设施（<= 6 比特用密集酉矩阵，> 6 比特用高效置换），因此量子比特的节省完全来自消除计数寄存器。

• 编码：与底层策略相同（群索引）
• 量子比特：2 + n_bits + 辅助量子比特（对比 2t + n_bits + 辅助量子比特）
• 权衡：需要动态电路（中间电路测量、重置、经典条件门）。在 IBM Heron r2 上最多支持 7 比特；8 比特及以上时，经典反馈同步开销超出 QPU 时间预算

策略 6：行波进位模加法（--oracle ripple）

在 ripple_carry_shor.py 中实现。使用 CDKM 行波进位加法器（Cuccaro 等人，2004）进行受控点加法，替换了密集酉矩阵和循环分解对换电路。

在群索引编码中，点 P = kG 由其循环群中的索引 k 表示。加上 S = sG 变为经典常数 s 的模加法（模 n）。关键见解：每个受控点加法简化为一个已知常数的单次受控模加法，通过 Qiskit 的 CDKMRippleCarryAdder 和 IntegerComparator 实现。

预言机由 2m 个受控模加法组成（每个计数寄存器 m 个），其中每个受控模加执行：

1. 加载常数到辅助量子比特寄存器，通过从控制量子比特的 CX 门
2. CDKM 半加器将辅助量子比特加到累加器中（仅最近邻门）
3. 整数比较器检测溢出（acc >= n）
4. 条件减法通过标志控制的加法将 2^m1 - n 加上
5. 标志反计算通过基于进位的探测

电路构建中不使用私钥 d 的知识。G 的幂的群索引计算为 2^i mod n（公开）。Q 的幂的群索引来自 G 生成的循环群的公开枚举——点 Q 在此枚举中查找。

• 编码：群索引 (0..n-1)
• 量子比特：4m + 5，其中 m = ceil(log2(n))
• 每次加法门数：O(m) 个 CDKM 操作，每个 O(m) 个 CX 门
• 总 CX 缩放：O(m^3)
• 硬件映射：CDKM 仅使用最近邻门，在 IBM 重六边形拓扑上路由开销约为 1x（对比 QFT 加法器的 26-33x）

比较

QFT 算术原语

代码库包含基于 QFT 的模算术构建块（Beauregard/Draper 加法器、量子-量子模乘法、模逆/取反），作为迈向 256 位全算术坐标编码的基础。这些原语已通过 Statevector 模拟验证，对于素数 p=13 以下的情况正确无误。

结果

成功在 IBM 量子硬件上恢复了挑战曲线（最高 17 比特）的私钥：

所有运行均在 IBM Quantum 开放实例计划上执行，该计划每月提供 10 分钟的免费量子计算。完整执行日志位于 executions/ 文件夹中。

行波进位策略（策略 6）实现了重大飞跃：从 10 比特（40 个量子比特，200 万个门）到 17 比特（69 个量子比特，11.2 万个门）——密钥大小增加 7 比特，而双量子比特门数减少了 18 倍。CDKM 加法器的最近邻门结构高效映射到 IBM 的重六边形拓扑，使路由开销保持在 1 倍左右。

半经典 PE：IBM 硬件上的动态电路

半经典策略（--oracle google）通过使用 IBM Heron r2 处理器上的动态电路（中间电路 reset、经典条件 p 门，通过 if_test），在 4 比特、6 比特和 7 比特上成功恢复了密钥。在 7 比特时，电路仅使用 14 个量子比特（对比标准置换方法的 26 个），同时在转换后产生可比较的 2Q 门数。

在 8 比特及以上时，半经典方法在当前的 IBM 硬件上变得不实用。尽管 if_else 和 reset 在 Heron r2 上得到支持（通过后端目标检查确认），但每个经典反馈点都需要完整的 QPU 同步——所有 156 个物理量子比特必须空闲，而经典控制器处理 ~16 个活跃量子比特的条件。具有 16 个以上反馈点的 ~295K CZ 门使得每次执行的运行开销超出 QPU 时间预算。标准置换方法将相同门数作为单个连续批次运行，无需动态电路，在此规模下成功完成。

近似 QFT 截断（max_corrections 参数）将 if_else 块的数量从 O(n^2) 减少到 O(n)，方法是为每个测量步骤仅保留最近的 k 个相位校正（超过 k 的角度贡献小于 pi/2^{k+1}，低于硬件噪声底限）。当 max_corrections=1 时，8 比特电路有 16 个 if_else 块——在此门数下仍足以在 IBM 硬件上导致超时。

噪声与保真度分析

估算电路保真度

假设典型 IBM 量子双量子比特 (CX) 门保真度约为 99.5%，估算的电路保真度随门数呈指数下降：

电路保真度计算为 F ≈ (0.995)^{CX_count}。对于超过 4 比特的所有情况，估算的保真度极小——输出分布主要受噪声支配。

为何仍然有效

对于 8 比特及以上，每次射击产生几乎唯一的比特串（8 比特时 8,192 次射击中有 8,128 个唯一结果；16 比特和 17 比特时，20,000 个结果全部唯一）。在比特串级别，输出与均匀随机采样难以区分。然而，该算法仍然恢复正确的私钥。

关键在于 Shor 的后处理对噪声具有鲁棒性，而原始比特串分析则不然。每次射击产生一个 (j, k, r) 测量三元组。提取过程计算 d_cand = (r - j) · k^{-1} mod n 并通过 d_cand · G == Q 验证。只有真正的 d 能通过椭圆曲线验证，因此在数千个噪声射击中，即使只有一个正确的候选也足够了。

纯随机的 (j, k, r) 三元组产生正确 d_cand 的概率约为 1/n。对于 S 次射击，仅由噪声产生的验证命中数的期望值为 ~S/n。在 17 比特 (n=65,173, S=20,000) 时，这给出约 0.3 个预期噪声命中——在此规模下的任何成功恢复都提供了超越经典噪声底限的量子信号证据。

对于较小的曲线，当射击次数 >> n 时（例如，10 比特，n=547，1,024 次射击），噪声底限约为每个候选 1,024/547 ≈ 1.9 票。即使少数携带信号的射击也能将正确的 d 推到噪声底限之上。这解释了尽管电路保真度看似使计算不可能，但算法仍然成功的原因。

量子信号 vs 经典噪声

在玩具规模上，提取的验证步骤 (d_cand * G == Q) 充当过滤器，只接受真正的 d。这意味着即使是纯随机的 (j, k, r) 三元组，每次运行也能以大约 shots / n 的比率产生有效的候选。当 shots >> n 时，仅凭随机噪声就有很高概率恢复 d。

为了测试量子电路是否贡献了超出此经典噪声底限的信号，我们在 ibm_kingston 上以仅 8 次射击（远低于群阶）运行了 6 比特挑战 (n=31)，重复 10 次：

结果：4/10 成功 (40%)，对比经典噪声基线约 20%（通过蒙特卡洛模拟计算：8 个随机比特串，(r-j)*k_inv mod 31 通过验证过滤）。单尾二项检验：P(X >= 4 | n=10, p=0.20) = 0.121，表示比噪声底限提高了 2 倍。虽然单独来看在 p < 0.05 水平上不具统计显著性（需要 5 次或更多成功），但观察到的比率与量子信号每次运行贡献约 1-2 个额外有效 (j, k) 对的预期一致，超出了随机机会提供的数量。

该结果介于经典噪声底限和理论量子优势区间之间。在更大的曲线规模下，当 n >> shots 时，噪声基线降至 1% 以下，任何成功的密钥恢复都将成为量子计算的强有力证据。

快速开始```bash

git clone https://github.com/GiancarloLelli/quantum.git cd quantum

python -m venv . Scripts\Activate.ps1 # For Windows only

pip install -r requirements.txt

### 如何运行

你需要一个 [IBM Quantum](https://quantum.ibm.com/) 账户。首次运行时传入你的 API token，它将被保存在本地：```bash
# Solve the 4-bit challenge curve:
python projecteleven.py --challenge 4 --token YOUR_IBM_TOKEN --backend ibm_marrakesh

# Subsequent runs (token already saved):
python projecteleven.py --challenge 4 --backend ibm_marrakesh

# Use the coordinate-based quantum oracle:
python projecteleven.py --challenge 4 --oracle coordinate --backend ibm_marrakesh

# Use the arithmetic oracle (coordinate encoding + QFT primitives):
python projecteleven.py --challenge 4 --oracle arithmetic --backend ibm_marrakesh

# Use ripple-carry modular addition (CDKM — best for 8-bit+):
python projecteleven.py --challenge 16 --oracle ripple --backend ibm_fez --shots 20000

# Use Google semiclassical phase estimation (qubit-recycled):
python projecteleven.py --challenge 4 --oracle google --backend ibm_marrakesh

# Use a specific IBM Quantum instance:
python projecteleven.py --challenge 4 --instance ibm-q/open/main --backend ibm_marrakesh

# Verify curve parameters without quantum execution:
python projecteleven.py --curve curve_4 --verify-only

CLI 选项

项目结构```

projecteleven.py # Shor solver — dense unitary approach + CLI entry point quantum_arithmetic.py # Efficient permutation decomposition + QFT arithmetic primitives quantum_oracle.py # Coordinate-based oracle + arithmetic oracle framework google_semiclassical.py # Google semiclassical PE — qubit-recycled phase estimation ripple_carry_shor.py # Ripple-carry modular addition oracle (CDKM) — best for 8-bit+ input_curves.json # Challenge curves (4-bit to 30-bit) problem/curves.py # Curve generation utility requirements.txt # qiskit, qiskit-ibm-runtime

## 参考文献

- P. Shor, ["量子计算中的离散对数与因子分解算法"](https://arxiv.org/abs/quant-ph/9508027) (1994)
- S. Beauregard, ["使用2n+3量子比特的Shor算法电路"](https://arxiv.org/abs/quant-ph/0205095) (2003)
- S. A. Cuccaro, T. G. Draper, S. A. Kutin, D. P. Moulton, ["一种新的量子行波进位加法电路"](https://arxiv.org/abs/quant-ph/0410184) (2004)
- M. Roetteler, M. Naehrig, K. Svore, K. Lauter, ["计算椭圆曲线离散对数的量子资源估计"](https://arxiv.org/abs/1706.06752) (2017)
- R. Griffiths, C.-S. Niu, ["量子计算的半经典傅里叶变换"](https://arxiv.org/abs/quant-ph/9511007) (1996)
- R. Babbush 等, ["抵御量子攻击的椭圆曲线加密货币保护：资源估计与缓解措施"](https://quantumai.google/static/site-assets/downloads/cryptocurrency-whitepaper.pdf) (2026)

## 许可证

本项目是提交至Q-Day奖项挑战赛的成果，以[MIT许可证](https://github.com/yuvadm/quantumslop/blob/main/LICENSE)发布。