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

该存储库包含 Qiskit 代码，用于对椭圆曲线离散对数场景中使用的空间高效量子模逆与仿射点加法线路进行资源估算。

当前代码库以三个工作流为核心：

模逆线路的分块递归计数；
线路的可选局部 NCT 模板优化；
封装仿射点加法线路的编译后分块资源估算。

存储库结构

.
├── README.md
│
├── eea_model/: original classical EEA reference implementation used for algorithm prototyping and correctness validation.
│
├── run_eea_s835_fastdual_recursive_chunks_checkpoint.py
├── run_eea_s835_fastdual_recursive_chunks_checkpoint_nctopt.py
├── count_s835_fastdual_wrapped_point_addition_blocks_compiled.py
│
├── eea_circuit.py
├── eea_circuit_s835_fastdual.py
├── eea_circuit_s835_lowaux.py
├── eea_circuit_updated.py
├── under1000_eea_shared_s835_fastdual_wrapped.py
├── under1000_modular_arithmetic_base.py
│
├── point_addition_fig14_s835_fastdual_wrapped_quadratic.py
├── quadratic_fig15_inplace_s835_fastdual_wrapped.py
├── quadratic_gidney_arithmetic.py
├── quadratic_lazy_instruction.py
├── quadratic_modular_arithmetic.py
├── quadratic_squ_minus.py
│
├── ccx_recursive_block_counter.py
├── nct_template_segment_optimizer.py
│
├── test_eea_strict_main.py
└── test_point_addition_strict_main.py

主要入口脚本

run_eea_s835_fastdual_recursive_chunks_checkpoint.py
以检查点分块方式递归计数 EEA 算法 3 的步骤。
run_eea_s835_fastdual_recursive_chunks_checkpoint_nctopt.py
与上述 EEA 计数工作流相同，但额外进行局部 NCT 模板优化。
count_s835_fastdual_wrapped_point_addition_blocks_compiled.py
通过递归计数可复用的已编译子块，并以精确重数组装重复的算术部件，对封装点加法线路进行计数。

EEA 文件

eea_circuit_s835_fastdual.py：生产级 EEA 线路的主要实现。
eea_circuit_s835_lowaux.py：主实现使用的低辅助量子比特辅助例程。
eea_circuit_updated.py：共享的 EEA 构建模块与递归资源计数工具。
eea_circuit.py：用于测试的向后兼容包装器。

点加法与算术文件

point_addition_fig14_s835_fastdual_wrapped_quadratic.py：构建与图 14 调度对应的封装仿射点加法线路。
quadratic_fig15_inplace_s835_fastdual_wrapped.py：构建图 15 的就地除法与就地乘法结构，包含 EEA、乘法、测量、重置和前馈相位校正。
quadratic_modular_arithmetic.py：点加法计数器使用的模加/模减、乘法、逆乘法、倍增和减半指令。
quadratic_gidney_arithmetic.py：二次模算术层使用的 Gidney 风格算术原语以及测量与前馈辅助函数。
quadratic_squ_minus.py：仿射点加法调度中使用的平方减（square-minus）块。
under1000_eea_shared_s835_fastdual_wrapped.py：点加法线路使用的共享 EEA 封装器与辅助函数。
under1000_modular_arithmetic_base.py：小型共享模算术工具。

计数与优化工具

ccx_recursive_block_counter.py：Qiskit 线路的递归计数器，支持 MCX 展开与 SWAP 展开策略。
nct_template_segment_optimizer.py：针对 {X, CX, CCX} 段的局部基于模板的优化器。

环境要求

推荐环境：

Python 3.10+
Qiskit

安装主要依赖：

python -m pip install --upgrade pip
python -m pip install qiskit

快速开始

运行测试套件：

python test_eea_strict_main.py
python test_point_addition_strict_main.py

如需更快的点加法冒烟测试：

python test_point_addition_strict_main.py --skip-n256 --skip-report

1. EEA 递归分块计数

标准 EEA 计数入口为：

python run_eea_s835_fastdual_recursive_chunks_checkpoint.py \
  --n 192 \
  --chunk-size 25 \
  --measurement-uncompute \
  --resume \
  --workdir eea_s835_fastdual_chunks25 \
  --out eea_s835_fastdual_algorithm3_recursive_chunks_n192_measurement.json

重要参数：

--n：位宽。
--T-max：可选，覆盖算法 3 的步数；默认使用 eea.get_n_config(n) 中的值。
--chunk-size：每个检查点分块计数的算法 3 步数。
--aux-size：可选，覆盖辅助量子比特池的大小；若省略，则自动计算布局辅助大小。
--measurement-uncompute：在计数的 EEA 块中启用基于测量的反计算。
--resume：复用 --workdir 中已有的非空分块 JSON 文件。
--workdir：存放各分块检查点文件的目录。
--out：每个分块完成后写入的累计 JSON 汇总。

脚本会写入诸如以下的分块文件：

eea_s835_fastdual_chunks25/eea_s835_fastdual_n192_T0001_0025.json

以及包含如下字段的累计输出 JSON：

mode
n
T_max
num_qubits
len_width
shift_width
aux_size
measurement_based
ops
chunks
elapsed_s_so_far

2. 带 NCT 模板优化的 EEA 计数

优化计数入口为：

python run_eea_s835_fastdual_recursive_chunks_checkpoint_nctopt.py \
  --n 128 \
  --chunk-size 25 \
  --measurement-uncompute \
  --templates small-nct \
  --rounds 1 \
  --max-nct-segment-gates 40 \
  --segment-timeout-s 10 \
  --timeout-mode auto \
  --resume \
  --workdir eea_s835_fastdual_chunks_nctopt_failopen_r1_128_seg40_to10 \
  --out eea_s835_fastdual_algorithm3_recursive_chunks_n128_measurement_nctopt_failopen_r1_seg40_to10.json

该工作流尝试对 {X, CX, CCX} 段进行局部模板优化。它被设计为有界的故障开放（fail-open）计数器：如果某个优化步骤超时或抛出异常，该步骤将在不进行模板轮次的情况下被精确计数，然后写入检查点，因此最终报告的计数保持完整。

除标准 EEA 参数外，有用的参数：

--templates {small-nct,all-nct}：模板库选择。
--rounds：模板优化轮数。
--max-nct-segment-gates：发送至模板优化的可逆段的最大大小。
--max-nct-segment-qubits：段中的最大量子比特数。
--segment-timeout-s：单段优化的超时时间。
--step-timeout-s：整个算法 3 步骤在回退为未改变计数前的超时时间。
--fallback-step-timeout-s：精确回退计数的超时时间。
--force：即使步骤/分块检查点已存在也重新计算。
--ignore-policy-mismatch：即使优化策略不同也复用旧检查点；主要用于调试。

优化工作流会在以下目录写入步骤级检查点：

<workdir>/steps/

并在以下目录写入分块级汇总：

<workdir>/

3. 封装点加法的编译后分块计数

点加法计数器依赖于上述某个 EEA 工作流生成的算法 3 计数 JSON。点加法计数器的 --n 值应与 EEA JSON 中的 n 字段一致。

以 n=64 为例：

python run_eea_s835_fastdual_recursive_chunks_checkpoint.py \
  --n 64 \
  --chunk-size 25 \
  --measurement-uncompute \
  --resume \
  --workdir eea_s835_fastdual_chunks25_n64 \
  --out eea_s835_fastdual_algorithm3_recursive_chunks_n64_measurement.json

然后运行：

python count_s835_fastdual_wrapped_point_addition_blocks_compiled.py \
  --n 64 \
  --eea-steps-json eea_s835_fastdual_algorithm3_recursive_chunks_n64_measurement.json \
  --out point_addition_s835_fastdual_wrapped_blocks_compiled_counts_n64.json

以优化后的 n=128 EEA 输出为例：

python count_s835_fastdual_wrapped_point_addition_blocks_compiled.py \
  --n 128 \
  --eea-steps-json eea_s835_fastdual_algorithm3_recursive_chunks_n128_measurement_nctopt_failopen_r1_seg40_to10.json \
  --out point_addition_s835_fastdual_wrapped_blocks_compiled_counts_n128.json

重要参数：

--n：位宽。
--p：模数；默认为 secp256k1 素数。
--s-qubits：可选，覆盖共享 EEA 算术寄存器的大小。
--point-constant {secp256k1-generator,zero,custom}：用于图 14 常数坐标更新的点常数选择。
--x2、--y2：自定义点坐标；使用 --point-constant custom 时必填。
--eea-steps-json：包含递归算法 3 EEA 计数的 JSON 文件。
--allow-eea-n-mismatch：仅用于调试的覆盖项，允许 EEA JSON 中的 n 与请求的 --n 不同。
--mcx-policy {clean-vchain,keep}：递归计数使用的 MCX 展开策略。
--validate-full-mul：对于较小的 n，递归计数完整乘法/平方定义，并与组装后的块计数进行比较。

输出报告包含：

counting_mode
n
p
point_constant_kind
qiskit_width_report
eea_meta
block_summaries
raw_block_counters
key_ccx
validation
elapsed_s

点加法计数器构建可复用的 Qiskit 线路，在 {CCX, CX, X} 基下递归计数，然后组装更大的重复块，如乘法、逆乘法、就地除法、就地乘法、平方减，以及总的图 14 点加法块。

测试

本存储库包含两个纯 Python 测试驱动程序。它们特意不使用 pytest、Aer 或完整的态矢量模拟来编写。测试在适当之处递归展开 Qiskit 定义，并对 Toffoli 网络块模拟计算基态。

EEA 严格测试

EEA 测试位于：

test_eea_strict_main.py

运行默认 EEA 测试套件：

python test_eea_strict_main.py

默认套件检查：

实现不是小 n 端点捷径；
算法 3 虚线块调度存在；
多个小宽度上的活动窗口公式；
一元迭代、前置/后置移位、相位更新、位置控制交换和长度更新块；
默认素数 3, 5, 7, 11, 13, 17 的算法 3 端点，同时使用精确步数和固定 T_max；
小默认素数 3, 5, 7 的完整算法 1 包装器。

有用的变体：

# Fast structural + block tests only.
python test_eea_strict_main.py --skip-endpoint --skip-alg1

# Include the heavier PDF/Table-4 p=37, x=13 trace benchmark.
python test_eea_strict_main.py --table4

# Test all x values for primes above 13 as well.
python test_eea_strict_main.py --primes 3 5 7 11 13 17 --mid-all-x --verbose

点加法严格测试

点加法测试位于：

test_point_addition_strict_main.py

运行默认点加法测试套件：

python test_point_addition_strict_main.py

默认点加法套件检查：

封装点加法寄存器布局；
n=256 宽度的恒等式 835 = 1 + 3*256 + 66；
图 14/图 15 顶层操作顺序；
涉及 H、measure、reset、经典控制的 Z 和 swap 操作的显式动态线路结构；
小模数的编译算术子块组装；
使用合成算法 3 JSON 的微型集成点加法计数器报告，从而在不运行大型 EEA 计数的情况下测试报告路径。

大素数回归矩阵覆盖域位宽 n 与素数模数 p 的代表性组合，范围从 12 位到 512 位素域。测试实例包括例如 n=16, p=65521、n=32, p=4294967291、n=256 时的 secp256k1 素数，以及 n=128, 160, 192, 224, 384, 512 的代表性素数。

对于每个 (n,p) 组合，测试包括边界、对称、随机和相对较长的 EEA 轨迹。完整编译算术组装仅对选定的中等宽度实例运行，而较大的 (n,p) 组合用于验证线路构建、寄存器布局、调度和递归资源计数路径。

有用的变体：

# Skip the tiny integrated report and only check construction/schedule/assembly.
python test_point_addition_strict_main.py --skip-report

# Fast smoke test that also skips the n=256 width construction check.
python test_point_addition_strict_main.py --skip-n256 --skip-report

# Use a different small prime/width for compiled-block validation.
python test_point_addition_strict_main.py --n 5 --p 17

如果未安装 Qiskit，test_point_addition_strict_main.py 会打印一条跳过提示并以成功状态退出。EEA 严格测试需要 Qiskit，因为它会构建 EEA/PDF 块门。

复现主要统计数据

我们的论文报告了以下数值资源估算结果：

n = 64, 128, 160, 192, 224, 256, 384, 512

典型工作流为：

对给定 n 运行 EEA 算法 3 计数器；
（可选）对同一 n 运行 NCT 优化版本；
将得到的 EEA JSON 传给封装点加法计数器；
从输出报告中收集 key_ccx、block_summaries 和 qiskit_width_report 字段。

对于较大的宽度，请使用 --resume 并保留 --workdir 目录，因为分块和步骤检查点旨在支持中断的长时运行。

引用

如果您在研究中使用本代码库，请引用：

@misc{luo2026quantumalgorithmellipticcurve,
      title={Quantum Algorithm for Elliptic Curve Discrete Logarithms with Space-Efficient Point Addition}, 
      author={Han Luo and Ziyi Yang and Jingquan Luo and Ziruo Wang and Yuexin Su and Xiaoming Sun and Lvzhou Li and Tongyang Li},
      year={2026},
      eprint={2607.13816},
      archivePrefix={arXiv},
      primaryClass={quant-ph},
      url={https://arxiv.org/abs/2607.13816}, 
}

Quantum-Algorithm-for-Elliptic-Curve-Discrete-Logarithms-with-Space-Efficient-Point-Addition

最受欢迎