Shor算法用于ECDLP — Q-Day Prize提交

量子求解器，用于解决椭圆曲线离散对数问题（ECDLP），为Q-Day Prize Challenge by 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系列一致。求解器实现了用于ECDLP的Shor算法的双寄存器变体：

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

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

Oracle策略

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

用于群阶最高约6比特的曲线。在 projecteleven.py 中实现。

每个受控点加法"add S"表示为通过 qc.unitary() 应用的 2^(n+1) x 2^(n+1) 置换矩阵。该矩阵编码了完整的群作用：左上角块是单位矩阵（控制=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给出O(n)个Toffoli门，而不是没有辅助比特时的O(n^2)。每个受控加法构建为独立的子电路，并作为一个单一不透明门附加，避免了Qiskit中的二次DAG增长。

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

策略3：基于坐标的量子Oracle (--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"根据所有有效坐标编码上的EC加法公式计算，产生坐标寄存器上的置换。此置换使用与策略2相同的CNOT归约+MCX基础设施分解为对换。

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

策略4：算术Oracle (--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 et al.（2026）中应用于secp256k1 ECDLP资源估计。Babbush等人的论文于2026年3月30日发表。

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

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

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

策略6：行波进位模加法 (--oracle ripple)

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

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

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

1. 加载常数 到辅助寄存器，通过来自控制量子比特的CX
2. CDKM半加法器 将辅助加到累加器（仅最近邻门）
3. 整数比较器 检测溢出（acc >= n）
4. 条件减法 of n 通过标志控制的 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重六角拓扑上给出约1倍布线开销（而基于QFT的加法器为26-33倍）

比较

QFT算术原语

代码库包含基于QFT的模算术构建块（Beauregard/Draper加法器、量子-量子模乘法、模逆/取反），作为未来朝着256比特完全算术坐标编码的基础。这些原语已通过Statevector模拟对p=13以内的素数验证正确性。

结果

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

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

行波进位策略（策略6）实现了重大飞跃：从10比特（40量子比特，2M门）到17比特（69量子比特，112K门）——密钥大小增加7比特，同时双量子比特门数减少18倍。CDKM加法器的最近邻门结构高效映射到IBM的重六角拓扑，将布线开销保持在接近1倍。

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

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

在8比特及以上，半经典方法在当前IBM硬件上变得不切实际。尽管 if_else 和 reset 在Heron r2上得到支持（通过后端目标检查确认），每个经典反馈点需要完整的QPU同步——所有156个物理量子比特必须空闲，而经典控制器为约16个活跃量子比特处理条件。约295K个CZ门分布在16个以上反馈点，每次运行的开销使任务超过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通过EC验证，因此即使在数千个噪声运行中只有一个正确候选也足够。

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

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

量子信号与经典噪声

在玩具规模下，提取的验证步骤（d_cand * G == Q）充当一个过滤器，只接受真实的 d。这意味着即使纯随机的 (j, k, r) 三元组也将以大约 shots / n 每轮的速度产生有效候选。当 shots >> n 时，仅随机噪声就可以高概率恢复d。

为了测试量子电路是否提供了超出此经典噪声底限的信号，我们在ibm_kingston上使用仅8次运行（远低于群阶）10次运行了6比特挑战（n=31）：

结果：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 令牌，它将被保存在本地：```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

## References

- P. Shor, ["量子计算算法：离散对数与因式分解"](https://arxiv.org/abs/quant-ph/9508027) (1994)
- S. Beauregard, ["使用2n+3量子比特的肖尔算法电路"](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)

## License

本项目是提交至 Q-Day Prize Challenge 的作品，采用 [MIT 许可证](https://github.com/giancarlolelli/quantum/blob/main/LICENSE) 发布。