Algorithme quantique pour les logarithmes discrets sur courbes elliptiques avec addition de points économe en espace

Ce dépôt contient du code Qiskit pour l'estimation des ressources des circuits quantiques économes en espace d'inversion modulaire et d'addition de points affine, utilisés dans le cadre des logarithmes discrets sur courbes elliptiques.

La base de code actuelle est centrée sur trois flux de travail :

1. le comptage récursif par blocs du circuit d'inversion modulaire ;
2. l'optimisation locale facultative par modèles NCT du circuit ;
3. l'estimation compilée bloc par bloc des ressources du circuit enveloppé d'addition de points affine.

Structure du dépôt

.
├── 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

Scripts d'entrée principaux

• run_eea_s835_fastdual_recursive_chunks_checkpoint.py
  Compte récursivement les étapes de l'algorithme 3 de l'EEA, par blocs avec points de contrôle.

• run_eea_s835_fastdual_recursive_chunks_checkpoint_nctopt.py
  Même flux de travail de comptage EEA, mais avec optimisation locale par modèles NCT.

• count_s835_fastdual_wrapped_point_addition_blocks_compiled.py
  Compte le circuit enveloppé d'addition de points en comptant récursivement les sous-blocs compilés réutilisables et en assemblant les composants arithmétiques répétés avec des multiplicités exactes.

Fichiers EEA

• eea_circuit_s835_fastdual.py: Implémentation principale du circuit EEA de production.
• eea_circuit_s835_lowaux.py: Routines d'assistance à faible nombre de qubits auxiliaires utilisées par l'implémentation principale.
• eea_circuit_updated.py: Blocs de construction EEA partagés et utilitaires récursifs de comptage des ressources.
• eea_circuit.py: Wrapper de rétrocompatibilité pour les tests.

Fichiers d'addition de points et d'arithmétique

• point_addition_fig14_s835_fastdual_wrapped_quadratic.py : construit le circuit enveloppé d'addition de points affine correspondant à l'ordonnancement de la Fig.14.
• quadratic_fig15_inplace_s835_fastdual_wrapped.py : construit la structure de division en place et de multiplication en place de la Fig.15 avec EEA, multiplication, mesure, réinitialisation (reset) et correction de phase par anticipation.
• quadratic_modular_arithmetic.py : instructions d'addition/soustraction modulaire, de multiplication, de multiplication inverse, de doublement et de division par deux utilisées par le compteur d'addition de points.
• quadratic_gidney_arithmetic.py : primitives arithmétiques de style Gidney et outils de mesure et d'anticipation (feed-forward) utilisés par la couche arithmétique modulaire quadratique.
• quadratic_squ_minus.py : bloc square-minus utilisé dans l'ordonnancement de l'addition de points affine.
• under1000_eea_shared_s835_fastdual_wrapped.py : wrapper EEA partagé et outil d'assistance utilisés par le circuit d'addition de points.
• under1000_modular_arithmetic_base.py : petits utilitaires partagés d'arithmétique modulaire.

Utilitaires de comptage et d'optimisation

• ccx_recursive_block_counter.py : compteur récursif pour les circuits Qiskit, avec des politiques d'expansion MCX et d'expansion SWAP.
• nct_template_segment_optimizer.py : optimiseur local basé sur des modèles pour les segments {X, CX, CCX}.

Prérequis

Environnement recommandé :

• Python 3.10+
• Qiskit

Installez la dépendance principale avec :

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

Démarrage rapide

Exécutez la suite de tests :

python test_eea_strict_main.py
python test_point_addition_strict_main.py

Pour un test de fumée plus rapide de l'addition de points :

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

1. Comptage récursif par blocs de l'EEA

Le point d'entrée standard du comptage EEA est :

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

Arguments importants :

• --n : largeur en bits.
• --T-max : remplacement facultatif du nombre d'étapes de l'algorithme 3 ; par défaut, la valeur de eea.get_n_config(n) est utilisée.
• --chunk-size : nombre d'étapes de l'algorithme 3 comptées par bloc de point de contrôle.
• --aux-size : remplacement facultatif du pool de qubits auxiliaires ; s'il est omis, la taille du registre auxiliaire de la disposition est calculée automatiquement.
• --measurement-uncompute : active la décomputation basée sur la mesure dans les blocs EEA comptés.
• --resume : réutilise les fichiers JSON de blocs non vides existants dans --workdir.
• --workdir : répertoire des fichiers de point de contrôle par bloc.
• --out : résumé JSON cumulatif écrit après chaque bloc.

Le script écrit des fichiers par bloc, par exemple :

eea_s835_fastdual_chunks25/eea_s835_fastdual_n192_T0001_0025.json

ainsi qu'un JSON de sortie cumulatif contenant des champs tels que :

mode
n
T_max
num_qubits
len_width
shift_width
aux_size
measurement_based
ops
chunks
elapsed_s_so_far

2. Comptage EEA avec optimisation par modèles NCT

Le point d'entrée du comptage optimisé est :

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

Ce flux de travail tente une optimisation locale par modèles sur les segments {X, CX, CCX}. Il est conçu comme un compteur fail-open borné : si une étape optimisée expire ou lève une exception, cette étape est comptée exactement, sans rondes de modèles, puis enregistrée dans un point de contrôle ; les comptes finaux rapportés restent ainsi complets.

Arguments utiles en plus des arguments EEA standard :

• --templates {small-nct,all-nct} : sélection de la bibliothèque de modèles.
• --rounds : nombre de rondes d'optimisation par modèles.
• --max-nct-segment-gates : taille maximale d'un segment réversible envoyé à l'optimisation par modèles.
• --max-nct-segment-qubits : nombre maximal de qubits dans un segment.
• --segment-timeout-s : délai d'expiration (timeout) pour l'optimisation d'un segment individuel.
• --step-timeout-s : délai d'expiration pour une étape entière de l'algorithme 3 avant de revenir au comptage sans modification.
• --fallback-step-timeout-s : délai d'expiration pour le comptage de repli exact.
• --force : force le recalcul même si les points de contrôle d'étapes/blocs existent déjà.
• --ignore-policy-mismatch : réutilise les anciens points de contrôle même lorsque la politique d'optimisation diffère ; principalement pour le débogage.

Le flux de travail optimisé écrit à la fois des points de contrôle au niveau des étapes sous :

<workdir>/steps/

et des résumés au niveau des blocs sous :

<workdir>/

3. Comptage compilé bloc par bloc de l'addition de points enveloppée

Le compteur d'addition de points dépend d'un JSON de l'algorithme 3 de l'EEA produit par l'un des flux de travail EEA ci-dessus. La valeur --n du compteur d'addition de points doit correspondre au champ n du JSON EEA.

Exemple pour 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

Puis exécutez :

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

Exemple avec la sortie EEA optimisée pour 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

Arguments importants :

• --n : largeur en bits.
• --p : modulus ; par défaut, le nombre premier secp256k1.
• --s-qubits : remplacement facultatif de la taille du registre arithmétique EEA partagé.
• --point-constant {secp256k1-generator,zero,custom} : sélection de la constante de point pour les mises à jour de coordonnées constantes de la Fig.14.
• --x2, --y2 : coordonnées de point personnalisées ; requises lorsque --point-constant custom est utilisé.
• --eea-steps-json : fichier JSON contenant les comptes EEA récursifs de l'algorithme 3.
• --allow-eea-n-mismatch : remplacement réservé au débogage permettant au n du JSON EEA de différer du --n demandé.
• --mcx-policy {clean-vchain,keep} : politique d'expansion MCX pour le comptage récursif.

Le rapport de sortie inclut :

counting_mode
n
p
point_constant_kind
qiskit_width_report
eea_meta
block_summaries
raw_block_counters
key_ccx
validation
elapsed_s

Le compteur d'addition de points construit des circuits Qiskit réutilisables, les compte récursivement dans la base {CCX, CX, X}, puis assemble des blocs répétés plus grands tels que la multiplication, la multiplication inverse, la division en place, la multiplication en place, le bloc square-minus et le bloc total d'addition de points de la Fig.14.

Tests

Ce dépôt inclut deux pilotes de test Python simples. Ils sont volontairement écrits sans pytest, Aer ni simulation complète de statevector. Les tests développent récursivement les définitions Qiskit lorsque c'est approprié et simulent des états de la base computationnelle pour les blocs de réseaux de Toffoli.

Tests EEA stricts

Les tests EEA se trouvent dans :

test_eea_strict_main.py

Exécutez la suite EEA par défaut avec :

python test_eea_strict_main.py

La suite par défaut vérifie :

• que l'implémentation n'est pas un raccourci de point final pour les petits n ;
• que l'ordonnancement en blocs en pointillés de l'algorithme 3 est présent ;
• les formules de fenêtre active (active-window) sur plusieurs petites largeurs ;
• les blocs d'itération unaire, de décalage pré/post, de mise à jour de phase, d'échange contrôlé par emplacement et de mise à jour de longueur ;
• les points finaux de l'algorithme 3 pour les nombres premiers par défaut 3, 5, 7, 11, 13, 17, en utilisant à la fois les comptes d'étapes exacts et un T_max fixe ;
• le wrapper complet de l'algorithme 1 pour les petits nombres premiers par défaut 3, 5, 7.

Variantes utiles :

# 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

Tests stricts d'addition de points

Les tests d'addition de points se trouvent dans :

test_point_addition_strict_main.py

Exécutez la suite d'addition de points par défaut avec :

python test_point_addition_strict_main.py

La suite d'addition de points par défaut vérifie :

• la disposition des registres de l'addition de points enveloppée ;
• l'identité de largeur 835 = 1 + 3*256 + 66 pour n=256 ;
• l'ordre des opérations de haut niveau des Fig.14/Fig.15 ;
• la structure explicite de circuit dynamique impliquant les opérations H, measure, reset, Z contrôlé classiquement et swap ;
• l'assemblage de sous-blocs arithmétiques compilés pour un petit modulus ;
• un rapport intégré minimal du compteur d'addition de points utilisant un JSON synthétique de l'algorithme 3, afin que le chemin du rapport soit testé sans exécuter un grand comptage EEA.

La matrice de régression des grands nombres premiers couvre des paires représentatives de la largeur de bits n du corps et du modulus premier p, allant de corps premiers de 12 bits à 512 bits. Les instances testées incluent, par exemple, n=16, p=65521, n=32, p=4294967291, le nombre premier secp256k1 à n=256, et des nombres premiers représentatifs à n=128, 160, 192, 224, 384, 512.

Pour chaque paire (n,p), les tests incluent des traces EEA aux limites, symétriques, aléatoires et relativement longues. L'assemblage complet de l'arithmétique compilée n'est exécuté que pour des instances sélectionnées de largeur modérée, tandis que les paires (n,p) plus grandes servent à valider la construction du circuit, la disposition des registres, l'ordonnancement et les chemins de comptage récursif des ressources.

Variantes utiles :

# 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

Si Qiskit n'est pas installé, test_point_addition_strict_main.py affiche un message d'ignorance et se termine avec succès. Le test EEA strict requiert Qiskit car il construit les portes de blocs EEA/PDF.

Reproduction des statistiques principales

Notre article rapporte des résultats numériques d'estimation des ressources pour :

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

Un flux de travail typique est :

1. exécuter le compteur de l'algorithme 3 de l'EEA pour un n donné ;
2. exécuter facultativement la version optimisée NCT pour le même n ;
3. transmettre le JSON EEA résultant au compteur d'addition de points enveloppée ;
4. collecter les champs key_ccx, block_summaries et qiskit_width_report du rapport de sortie.

Pour les grandes largeurs, utilisez --resume et conservez les répertoires --workdir, car les points de contrôle de blocs et d'étapes sont conçus pour prendre en charge les longues exécutions interrompues.

Citation

Si vous utilisez cette base de code dans vos recherches, veuillez citer :

@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}, 
}