zerowang030221/quantum-algorithm-for-elliptic-curve-discrete-logarithms-with-space-efficient-point-additionQiskit 기반의 리소스 추정 프레임워크로, 타원 곡선 이산 로그 알고리즘에 사용되는 공간 효율적인 양자 모듈러 역원 및 아핀 점 덧셈 회로를 대상으로 합니다.
이 저장소는 타원 곡선 이산 로그 설정에서 사용되는 공간 효율적 양자 모듈러 역원 및 아핀 점 덧셈 회로의 리소스 추정을 위한 Qiskit 코드를 포함합니다.
현재 코드베이스는 세 가지 워크플로우를 중심으로 구성됩니다:
.
├── 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 Algorithm-3 단계를 재귀적으로 계산합니다.
run_eea_s835_fastdual_recursive_chunks_checkpoint_nctopt.py
동일한 EEA 계산 워크플로우이지만 로컬 NCT 템플릿 최적화가 적용됩니다.
count_s835_fastdual_wrapped_point_addition_blocks_compiled.py
재사용 가능한 컴파일된 하위 블록을 재귀적으로 계산하고 정확한 다중도로 반복되는 산술 구성 요소를 조합하여 래핑된 점 덧셈 회로를 계산합니다.
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: Fig.14 스케줄에 해당하는 래핑된 아핀 점 덧셈 회로를 구축합니다.quadratic_fig15_inplace_s835_fastdual_wrapped.py: EEA, 곱셈, 측정, 리셋 및 피드포워드 위상 보정을 사용하여 Fig.15 제자리 나눗셈 및 제자리 곱셈 구조를 구축합니다.quadratic_modular_arithmetic.py: 점 덧셈 카운터에서 사용되는 모듈러 덧셈/뺄셈, 곱셈, 역곱셈, 두 배 및 반감 명령어.quadratic_gidney_arithmetic.py: 이차 모듈러 산술 레이어에서 사용되는 Gidney 스타일 산술 프리미티브 및 측정/피드포워드 도우미.quadratic_squ_minus.py: 아핀 점 덧셈 스케줄에서 사용되는 제곱-마이너스 블록.under1000_eea_shared_s835_fastdual_wrapped.py: 점 덧셈 회로에서 사용되는 공유 EEA 래퍼 및 도우미.under1000_modular_arithmetic_base.py: 작은 공유 모듈러 산술 유틸리티.ccx_recursive_block_counter.py: MCX 확장 및 SWAP 확장 정책을 포함한 Qiskit 회로용 재귀 카운터.nct_template_segment_optimizer.py: {X, CX, CCX} 세그먼트용 로컬 템플릿 기반 최적화기.권장 환경:
주요 종속성을 설치하려면:
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
표준 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: Algorithm-3 단계 수에 대한 선택적 재정의; 기본적으로 eea.get_n_config(n)의 값이 사용됩니다.--chunk-size: 체크포인트 청크당 계산되는 Algorithm-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
최적화된 계산 진입점:
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} 세그먼트에 대한 로컬 템플릿 최적화를 시도합니다. 이는 제한된 실패-개방 카운터로 설계되었습니다: 최적화 단계가 시간 초과되거나 예외를 발생시키면 해당 단계는 템플릿 라운드 없이 정확히 계산되고 체크포인트되므로 최종 보고된 카운트가 완전하게 유지됩니다.
표준 EEA 인수 외에 유용한 인수:
--templates {small-nct,all-nct}: 템플릿 라이브러리 선택.--rounds: 템플릿 최적화 라운드 수.--max-nct-segment-gates: 템플릿 최적화로 전송되는 가역 세그먼트의 최대 크기.--max-nct-segment-qubits: 세그먼트의 최대 큐비트 수.--segment-timeout-s: 개별 세그먼트 최적화 시간 제한.--step-timeout-s: 변경되지 않은 계산으로 대체되기 전 전체 Algorithm-3 단계 시간 제한.--fallback-step-timeout-s: 정확한 대체 계산 시간 제한.--force: 단계/청크 체크포인트가 이미 존재하더라도 재계산합니다.--ignore-policy-mismatch: 최적화 정책이 다르더라도 이전 체크포인트를 재사용합니다. 주로 디버깅용입니다.최적화된 워크플로우는 다음 아래에 단계별 체크포인트를 작성합니다:
<workdir>/steps/
그리고 다음 아래에 청크별 요약을 작성합니다:
<workdir>/
점 덧셈 카운터는 위의 EEA 워크플로우 중 하나에서 생성된 EEA Algorithm-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}: Fig.14 상수 좌표 업데이트를 위한 점 상수 선택.--x2, --y2: 사용자 정의 점 좌표; --point-constant custom 사용 시 필요.--eea-steps-json: 재귀 Algorithm-3 EEA 카운트를 포함하는 JSON 파일.--allow-eea-n-mismatch: EEA JSON n이 요청된 --n과 다를 수 있도록 허용하는 디버그 전용 재정의.--mcx-policy {clean-vchain,keep}: 재귀 계산을 위한 MCX 확장 정책.--validate-full-mul: 작은 n의 경우 전체 곱셈/제곱 정의를 재귀적으로 계산하고 조립된 블록 카운트와 비교합니다.--out: 출력 JSON 경로.출력 보고서에는 다음이 포함됩니다:
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} 기준으로 재귀적으로 계산한 다음 곱셈, 역곱셈, 제자리 나눗셈, 제자리 곱셈, 제곱-마이너스 및 전체 Fig.14 점 덧셈 블록과 같은 더 큰 반복 블록을 조립합니다.
이 저장소에는 두 개의 일반 Python 테스트 드라이버가 포함되어 있습니다. 이는 의도적으로 pytest, Aer 또는 전체 상태 벡터 시뮬레이션 없이 작성되었습니다. 테스트는 적절한 곳에서 Qiskit 정의를 재귀적으로 확장하고 Toffoli 네트워크 블록에 대한 계산 기반 상태를 시뮬레이션합니다.
EEA 테스트는 다음 파일에 있습니다:
test_eea_strict_main.py
기본 EEA 스위트를 실행하려면:
python test_eea_strict_main.py
기본 스위트는 다음을 확인합니다:
n 엔드포인트 바로 가기가 아닙니다.3, 5, 7, 11, 13, 17에 대한 Algorithm-3 엔드포인트. 정확한 단계 카운트 및 고정 T_max를 모두 사용합니다.3, 5, 7에 대한 전체 Algorithm-1 래퍼.유용한 변형:
# 빠른 구조적 + 블록 테스트만.
python test_eea_strict_main.py --skip-endpoint --skip-alg1
# 더 무거운 PDF/Table-4 p=37, x=13 추적 벤치마크 포함.
python test_eea_strict_main.py --table4
# 13보다 큰 소수에 대한 모든 x 값도 테스트.
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.H, measure, reset, 고전적으로 제어된 Z 및 swap 연산을 포함하는 명시적 동적 회로 구조.큰 소수 회귀 매트릭스는 필드 비트 폭 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) 쌍은 회로 구성, 레지스터 레이아웃, 스케줄링 및 재귀 리소스 계산 경로를 검증하는 데 사용됩니다.
유용한 변형:
# 소형 통합 보고서를 건너뛰고 구성/스케줄/조립만 확인.
python test_point_addition_strict_main.py --skip-report
# n=256 폭 구성 검사도 건너뛰는 빠른 스모크 테스트.
python test_point_addition_strict_main.py --skip-n256 --skip-report
# 컴파일된 블록 검증에 다른 작은 소수/폭 사용.
python test_point_addition_strict_main.py --n 5 --p 17
Qiskit이 설치되지 않은 경우 test_point_addition_strict_main.py는 건너뛰기 메시지를 출력하고 성공적으로 종료됩니다. EEA 엄격 테스트는 EEA/PDF 블록 게이트를 구축하므로 Qiskit이 필요합니다.
우리 논문은 다음에 대한 수치적 리소스 추정 결과를 보고합니다:
n = 64, 128, 160, 192, 224, 256, 384, 512
일반적인 워크플로우는 다음과 같습니다:
n에 대해 EEA Algorithm-3 카운터를 실행합니다.n에 대해 NCT 최적화 버전을 실행합니다.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},
}