zerowang030221/quantum-algorithm-for-elliptic-curve-discrete-logarithms-with-space-efficient-point-additionMarco de estimación de recursos basado en Qiskit para circuitos modulares de inversión y suma de puntos afines eficientes en espacio utilizados en algoritmos de logaritmo discreto en curvas elípticas.
Este repositorio contiene código Qiskit para la estimación de recursos de los circuitos cuánticos de inversión modular eficiente en espacio y suma de puntos afín utilizados en configuraciones de logaritmos discretos en curvas elípticas.
La base de código actual se centra en tres flujos de trabajo:
.
├── 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
Cuenta los pasos del Algoritmo-3 EEA recursivamente, en fragmentos con puntos de control.
run_eea_s835_fastdual_recursive_chunks_checkpoint_nctopt.py
Mismo flujo de trabajo de conteo EEA, pero con optimización local de plantilla NCT.
count_s835_fastdual_wrapped_point_addition_blocks_compiled.py
Cuenta el circuito de suma de puntos envuelto contando recursivamente subbloques compilados reutilizables y ensamblando los componentes aritméticos repetidos con multiplicidades exactas.
eea_circuit_s835_fastdual.py: Implementación principal del circuito EEA de producción.eea_circuit_s835_lowaux.py: Rutinas auxiliares de baja ayuda utilizadas por la implementación principal.eea_circuit_updated.py: Bloques de construcción EEA compartidos y utilidades recursivas de conteo de recursos.eea_circuit.py: Envoltorio de compatibilidad hacia atrás para pruebas.point_addition_fig14_s835_fastdual_wrapped_quadratic.py: construye el circuito de suma de puntos afín envuelto correspondiente al cronograma de la Fig.14.quadratic_fig15_inplace_s835_fastdual_wrapped.py: construye la estructura de división in situ y multiplicación in situ de la Fig.15 con EEA, multiplicación, medición, reinicio y corrección de fase feed-forward.quadratic_modular_arithmetic.py: instrucciones de suma/resta modular, multiplicación, multiplicación inversa, duplicación y reducción a la mitad utilizadas por el contador de suma de puntos.quadratic_gidney_arithmetic.py: primitivas aritméticas estilo Gidney y ayudantes de medición y feed-forward utilizados por la capa aritmética modular cuadrática.quadratic_squ_minus.py: bloque cuadrado-menos utilizado en el cronograma de suma de puntos afín.under1000_eea_shared_s835_fastdual_wrapped.py: envoltorio EEA compartido y ayudante utilizado por el circuito de suma de puntos.under1000_modular_arithmetic_base.py: pequeñas utilidades compartidas de aritmética modular.ccx_recursive_block_counter.py: contador recursivo para circuitos Qiskit, con políticas para expansión MCX y expansión SWAP.nct_template_segment_optimizer.py: optimizador local basado en plantillas para segmentos {X, CX, CCX}.Entorno recomendado:
Instale la dependencia principal con:
python -m pip install --upgrade pip
python -m pip install qiskit
Ejecute la suite de pruebas:
python test_eea_strict_main.py
python test_point_addition_strict_main.py
Para una prueba rápida de suma de puntos:
python test_point_addition_strict_main.py --skip-n256 --skip-report
El punto de entrada estándar para el conteo EEA es:
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
Argumentos importantes:
--n: ancho de bits.--T-max: anulación opcional del número de pasos del Algoritmo-3; por defecto se usa el valor de eea.get_n_config(n).--chunk-size: número de pasos del Algoritmo-3 contados por fragmento de punto de control.--aux-size: anulación opcional del grupo de qubits auxiliares; si se omite, el tamaño del diseño auxiliar se calcula automáticamente.--measurement-uncompute: habilita la anulación basada en medición en los bloques EEA contados.--resume: reutiliza archivos JSON de fragmentos existentes no vacíos en --workdir.--workdir: directorio para archivos de punto de control por fragmento.--out: resumen JSON acumulativo escrito después de cada fragmento.El script escribe archivos por fragmento como:
eea_s835_fastdual_chunks25/eea_s835_fastdual_n192_T0001_0025.json
y un JSON de salida acumulativo que contiene campos como:
mode
n
T_max
num_qubits
len_width
shift_width
aux_size
measurement_based
ops
chunks
elapsed_s_so_far
El punto de entrada para el conteo optimizado es:
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
Este flujo de trabajo intenta la optimización local de plantillas en segmentos {X, CX, CCX}. Está diseñado como un contador acotado con fallo abierto: si un paso optimizado agota el tiempo o genera una excepción, ese paso se cuenta exactamente sin rondas de plantilla y luego se marca como punto de control, por lo que los recuentos finales informados permanecen completos.
Argumentos útiles además de los argumentos EEA estándar:
--templates {small-nct,all-nct}: selección de biblioteca de plantillas.--rounds: número de rondas de optimización de plantillas.--max-nct-segment-gates: tamaño máximo de un segmento reversible enviado a optimización de plantillas.--max-nct-segment-qubits: número máximo de qubits en un segmento.--segment-timeout-s: tiempo de espera para la optimización de un segmento individual.--step-timeout-s: tiempo de espera para un paso completo del Algoritmo-3 antes de retroceder al conteo sin cambios.--fallback-step-timeout-s: tiempo de espera para el conteo de retroceso exacto.--force: recalcula incluso si ya existen puntos de control de paso/fragmento.--ignore-policy-mismatch: reutilizar puntos de control antiguos incluso si la política de optimización difiere; esto es principalmente para depuración.El flujo de trabajo optimizado escribe puntos de control a nivel de paso en:
<workdir>/steps/
y resúmenes a nivel de fragmento en:
<workdir>/
El contador de suma de puntos depende de un JSON del Algoritmo-3 EEA producido por uno de los flujos de trabajo EEA anteriores. El valor --n del contador de suma de puntos debe coincidir con el campo n en el JSON EEA.
Ejemplo para 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
Luego ejecute:
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
Ejemplo para la salida EEA optimizada n=128:
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
Argumentos importantes:
--n: ancho de bits.--p: módulo; por defecto el primo secp256k1.--s-qubits: anulación opcional del tamaño del registro aritmético EEA compartido.--point-constant {secp256k1-generator,zero,custom}: selección de constante de punto para las actualizaciones de coordenadas constantes de la Fig.14.--x2, --y2: coordenadas de punto personalizadas; requerido cuando se usa --point-constant custom.--eea-steps-json: archivo JSON que contiene los recuentos recursivos del Algoritmo-3 EEA.--allow-eea-n-mismatch: anulación solo para depuración que permite que el n del JSON EEA difiera del --n solicitado.--mcx-policy {clean-vchain,keep}: política de expansión MCX para conteo recursivo.El informe de salida incluye:
counting_mode
n
p
point_constant_kind
qiskit_width_report
eea_meta
block_summaries
raw_block_counters
key_ccx
validation
elapsed_s
El contador de suma de puntos construye circuitos Qiskit reutilizables, los cuenta recursivamente en la base {CCX, CX, X}, y luego ensambla bloques repetidos más grandes como multiplicación, multiplicación inversa, división in situ, multiplicación in situ, cuadrado-menos, y el bloque total de suma de puntos de la Fig.14.
Este repositorio incluye dos controladores de prueba simples en Python. Están escritos intencionalmente sin pytest, Aer o simulación completa de vector de estado. Las pruebas expanden recursivamente definiciones de Qiskit donde corresponde y simulan estados de base computacional para bloques de red de Toffoli.
Las pruebas EEA están en:
test_eea_strict_main.py
Ejecute la suite EEA predeterminada con:
python test_eea_strict_main.py
La suite predeterminada verifica:
n pequeño;3, 5, 7, 11, 13, 17, usando tanto recuentos de pasos exactos como T_max fijo;3, 5, 7.Variantes útiles:
# Solo pruebas estructurales y de bloque rápidas.
python test_eea_strict_main.py --skip-endpoint --skip-alg1
# Incluir la prueba de referencia más pesada de PDF/Table-4 p=37, x=13.
python test_eea_strict_main.py --table4
# Probar todos los valores x para primos mayores de 13 también.
python test_eea_strict_main.py --primes 3 5 7 11 13 17 --mid-all-x --verbose
Las pruebas de suma de puntos están en:
test_point_addition_strict_main.py
Ejecute la suite de suma de puntos predeterminada con:
python test_point_addition_strict_main.py
La suite de suma de puntos predeterminada verifica:
n=256 835 = 1 + 3*256 + 66;H, measure, reset, Z controlado clásicamente y swap;La matriz de regresión de primos grandes cubre pares representativos del ancho de bits de campo n y módulo primo p, que van desde campos de 12 bits hasta 512 bits. Las instancias probadas incluyen, por ejemplo, n=16, p=65521, n=32, p=4294967291, el primo secp256k1 en n=256, y primos representativos en n=128, 160, 192, 224, 384, 512.
Para cada par (n,p), las pruebas incluyen trazas EEA de límite, simétricas, aleatorias y relativamente largas. El ensamblaje aritmético compilado completo se ejecuta solo para instancias de ancho moderado seleccionadas, mientras que los pares (n,p) más grandes se utilizan para validar la construcción del circuito, el diseño del registro, la programación y las rutas recursivas de conteo de recursos.
Variantes útiles:
# Omitir el informe integrado pequeño y solo verificar construcción/programación/ensamblaje.
python test_point_addition_strict_main.py --skip-report
# Prueba rápida que también omite la verificación de construcción de ancho n=256.
python test_point_addition_strict_main.py --skip-n256 --skip-report
# Usar un primo/ancho pequeño diferente para la validación de bloques compilados.
python test_point_addition_strict_main.py --n 5 --p 17
Si Qiskit no está instalado, test_point_addition_strict_main.py imprime un mensaje de omisión y sale correctamente. La prueba estricta EEA requiere Qiskit porque construye las puertas de bloque EEA/PDF.
Nuestro artículo informa resultados numéricos de estimación de recursos para:
n = 64, 128, 160, 192, 224, 256, 384, 512
Un flujo de trabajo típico es:
n dado;n;key_ccx, block_summaries y qiskit_width_report del informe de salida.Para anchos grandes, use --resume y mantenga los directorios --workdir, ya que los puntos de control de fragmentos y pasos están diseñados para soportar ejecuciones largas interrumpidas.
Si utiliza esta base de código en su investigación, por favor cite:
@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},
}
--validate-full-mul: para n pequeño, cuenta recursivamente las definiciones completas de multiplicación/elevación al cuadrado y las compara con los recuentos de bloques ensamblados.--out: ruta del JSON de salida.