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 比特用高效置换），因此量子比特的节省完全来自消除计数寄存器。

曲线大小	标准量子比特数	半经典量子比特数	节省比例	硬件验证
4-bit (n=7)	11	5	55%	是
6-bit (n=31)	17	7	59%	是
7-bit (n=79)	26 + anc	14	46%	是
8-bit (n=139)	25 + anc	10 + anc	60%	否（QPU 同步开销）
10-bit (n=547)	31 + anc	12 + anc	61%	否（QPU 同步开销）

• 编码：与底层策略相同（群索引）
• 量子比特：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）

曲线大小	量子比特数	2Q 门数（转换后）	硬件验证
4-bit (n=7)	17	1,824	是（模拟）
8-bit (n=139)	37	11,224	—
10-bit (n=547)	45	17,204	—
12-bit (n=2143)	53	24,304	—
16-bit (n=32497)	65	98,049	是
17-bit (n=65173)	69	111,816	是

比较

指标	密集酉矩阵	高效置换	坐标预言机	算术预言机	半经典 PE	行波进位
点编码	群索引	群索引	(x, y, id_flag)	(x, y, id_flag)	群索引	群索引
每次加法缩放	O(4^n) 分解	O(N * n)	O(N * f_bits)	O(n^3) 渐近	O(N * n)	O(m^2)
量子比特 (4-bit)	11	13	24	24	5	17
量子比特 (6-bit)	17	21	36	36	9	25
2Q 门 (4-bit)	774	~1,200	6,449	6,449	~1,200	1,824
2Q 门 (6-bit)	23,471	~38,000	95,254	95,254	~38,000	4,582
实用范围	<= 6-bit	<= ~16-bit	<= 6-bit	>= 20-bit（未来）	<= ~16-bit	<= ~20-bit

QFT 算术原语

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

结果

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

挑战	p	n	策略	量子比特	2Q 门数	转换后深度	射击次数	后端	恢复的 d	作业 ID
4-bit	13	7	Dense unitary	11	774	2,425	8,192	ibm_torino	6	d73u28kvllmc73anvi90
4-bit	13	7	Coordinate oracle	24	6,449	13,125	8,192	ibm_kingston	6	d74ht798qmgc73fm32c0
4-bit	13	7	Arithmetic oracle	24	6,477	13,452	8,192	ibm_torino	6	d75648lbjrds73ec0eng
4-bit	13	7	Semiclassical PE	5	747	2,522	256	ibm_kingston	6	d75p1ftbjrds73ecne3g
6-bit	43	31	Dense unitary	17	23,471	72,475	8,192	ibm_torino	18	d73u2l5koquc73e24u8g
6-bit	43	31	Coordinate oracle	36	95,254	169,766	8,192	ibm_kingston	18	d74hu918qmgc73fm33g0
6-bit	43	31	Semiclassical PE	7	23,256	73,183	256	ibm_kingston	18	d75p1unq1anc738cmr6g
7-bit	67	79	Semiclassical PE	14	127,918	266,122	256	ibm_kingston	56	d75p3sq3qcgc73fs2fpg
8-bit	163	139	Efficient permutation	32	294,628	599,517	8,192	ibm_kingston	103	d73ui15koquc73e25e4g
9-bit	349	313	Efficient permutation	36	887,544	1,764,266	8,192	ibm_torino	135	d73ua2h8qmgc73flei9g
10-bit	547	547	Efficient permutation	40	2,049,138	3,948,250	1,024	ibm_torino	165	d752vfu8faus73evhovg
16-bit	32,803	32,497	Ripple-carry	65	98,049	202,994	20,000	ibm_fez	20,248	d790j2hq1efs73d2979g
17-bit	65,647	65,173	Ripple-carry	69	111,816	231,475	20,000	ibm_fez	1,441	d790krrc6das739idasg

所有运行均在 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 门数。