zerowang030221/quantum-algorithm-for-elliptic-curve-discrete-logarithms-with-space-efficient-point-additionQiskit-basiertes Ressourcenschätzungs-Framework für platzeffiziente Quanten-Modularinversion und affine Punktadditionsschaltungen, die in Algorithmen für diskrete Logarithmen auf elliptischen Kurven verwendet werden.
Dieses Repository enthält Qiskit-Code zur Ressourcenabschätzung der platzsparenden Quanten-Modular-Inversions- und affinen Punktadditionsschaltungen, die in elliptischen Kurven-Diskrete-Logarithmen-Szenarien verwendet werden.
Der aktuelle Codebestand konzentriert sich auf drei Arbeitsabläufe:
.
├── README.md
│
├── eea_model/: Originale klassische EEA-Referenzimplementierung, die für Algorithmen-Prototyping und Korrektheitsvalidierung verwendet wird.
│
├── 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
Zählt die EEA-Algorithmus-3-Schritte rekursiv in checkpointierten Chunks.
run_eea_s835_fastdual_recursive_chunks_checkpoint_nctopt.py
Gleicher EEA-Zählworkflow, jedoch mit lokaler NCT-Vorlagenoptimierung.
count_s835_fastdual_wrapped_point_addition_blocks_compiled.py
Zählt die umschlossene Punktadditionsschaltung durch rekursives Zählen wiederverwendbarer kompilierter Unterblöcke und Zusammenfügen der wiederholten arithmetischen Komponenten mit exakten Multiplizitäten.
eea_circuit_s835_fastdual.py: Hauptimplementierung der Produktions-EEA-Schaltung.eea_circuit_s835_lowaux.py: Hilfsroutinen mit geringem Hilfsqubit-Aufwand, die von der Hauptimplementierung verwendet werden.eea_circuit_updated.py: Gemeinsame EEA-Bausteine und rekursive Ressourcenzähl-Hilfsprogramme.eea_circuit.py: Abwärtskompatibilitäts-Wrapper für Tests.point_addition_fig14_s835_fastdual_wrapped_quadratic.py: Erstellt die umschlossene affine Punktadditionsschaltung entsprechend des Fig.14-Zeitplans.quadratic_fig15_inplace_s835_fastdual_wrapped.py: Erstellt die Fig.15-In-Place-Division und In-Place-Multiplikationsstruktur mit EEA, Multiplikation, Messung, Zurücksetzen und Feed-Forward-Phasenkorrektur.quadratic_modular_arithmetic.py: Modulare Additions-/Subtraktions-, Multiplikations-, inverse Multiplikations-, Verdopplungs- und Halbierungsinstruktionen, die vom Punktadditionszähler verwendet werden.quadratic_gidney_arithmetic.py: Gidney-artige arithmetische Primitive sowie Mess- und Feed-Forward-Helfer, die von der quadratischen modularen Arithmetikschicht verwendet werden.quadratic_squ_minus.py: Square-minus-Block, der im affinen Punktadditionsplan verwendet wird.under1000_eea_shared_s835_fastdual_wrapped.py: Gemeinsamer EEA-Wrapper und Helfer, der von der Punktadditionsschaltung verwendet wird.under1000_modular_arithmetic_base.py: Kleine gemeinsame modulare Arithmetik-Hilfsprogramme.ccx_recursive_block_counter.py: Rekursiver Zähler für Qiskit-Schaltungen mit Richtlinien für MCX-Expansion und SWAP-Expansion.nct_template_segment_optimizer.py: Lokaler vorlagenbasierter Optimierer für {X, CX, CCX}-Segmente.Empfohlene Umgebung:
Installieren Sie die Hauptabhängigkeit mit:
python -m pip install --upgrade pip
python -m pip install qiskit
Führen Sie die Testsuite aus:
python test_eea_strict_main.py
python test_point_addition_strict_main.py
Für einen schnelleren Punktadditions-Smoke-Test:
python test_point_addition_strict_main.py --skip-n256 --skip-report
Der Standard-Einstiegspunkt für die EEA-Zählung ist:
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
Wichtige Argumente:
--n: Bitbreite.--T-max: optionale Überschreibung für die Anzahl der Algorithmus-3-Schritte; standardmäßig wird der Wert von eea.get_n_config(n) verwendet.--chunk-size: Anzahl der Algorithmus-3-Schritte, die pro Checkpoint-Chunk gezählt werden.--aux-size: optionale Überschreibung für den Hilfsqubit-Pool; wenn nicht angegeben, wird die Layout-Hilfsgröße automatisch berechnet.--measurement-uncompute: Aktiviert messungsbasiertes Uncomputing in den gezählten EEA-Blöcken.--resume: Verwendet vorhandene nicht-leere Chunk-JSON-Dateien in --workdir erneut.--workdir: Verzeichnis für Checkpoint-Dateien pro Chunk.--out: Kumulative JSON-Zusammenfassung, die nach jedem Chunk geschrieben wird.Das Skript schreibt Dateien pro Chunk wie:
eea_s835_fastdual_chunks25/eea_s835_fastdual_n192_T0001_0025.json
und eine kumulative Ausgabe-JSON mit Feldern wie:
mode
n
T_max
num_qubits
len_width
shift_width
aux_size
measurement_based
ops
chunks
elapsed_s_so_far
Der optimierte Zähleinstiegspunkt ist:
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
Dieser Workflow versucht eine lokale Vorlagenoptimierung für {X, CX, CCX}-Segmente. Er ist als begrenzter Fail-Open-Zähler konzipiert: Wenn ein optimierter Schritt eine Zeitüberschreitung verursacht oder eine Ausnahme auslöst, wird dieser Schritt exakt ohne Vorlagenrunden gezählt und dann checkpointiert, sodass die endgültigen gemeldeten Zählungen vollständig bleiben.
Nützliche Argumente zusätzlich zu den Standard-EEA-Argumenten:
--templates {small-nct,all-nct}: Auswahl der Vorlagenbibliothek.--rounds: Anzahl der Vorlagenoptimierungsrunden.--max-nct-segment-gates: Maximale Größe eines reversiblen Segments, das zur Vorlagenoptimierung gesendet wird.--max-nct-segment-qubits: Maximale Anzahl von Qubits in einem Segment.--segment-timeout-s: Zeitüberschreitung für die Optimierung eines einzelnen Segments.--step-timeout-s: Zeitüberschreitung für einen gesamten Algorithmus-3-Schritt, bevor auf die unveränderte Zählung zurückgegriffen wird.--fallback-step-timeout-s: Zeitüberschreitung für die exakte Fallback-Zählung.--force: Berechnet auch dann neu, wenn Schritt-/Chunk-Checkpoints bereits existieren.--ignore-policy-mismatch: Verwendet alte Checkpoints erneut, selbst wenn die Optimierungsrichtlinie abweicht; dies dient hauptsächlich zum Debuggen.Der optimierte Workflow schreibt sowohl Schritt-Level-Checkpoints unter:
<workdir>/steps/
als auch Chunk-Level-Zusammenfassungen unter:
<workdir>/
Der Punktadditionszähler ist auf eine EEA-Algorithmus-3-JSON angewiesen, die von einem der obigen EEA-Workflows erzeugt wurde. Der --n-Wert des Punktadditionszählers sollte mit dem n-Feld in der EEA-JSON übereinstimmen.
Beispiel für 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
Führen Sie dann aus:
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
Beispiel für die optimierte n=128-EEA-Ausgabe:
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
Wichtige Argumente:
--n: Bitbreite.--p: Modul; standardmäßig die secp256k1-Primzahl.--s-qubits: optionale Überschreibung für die Größe des gemeinsamen EEA-Arithmetikregisters.--point-constant {secp256k1-generator,zero,custom}: Auswahl der Punktkonstanten für die Fig.14-Konstantenkoordinatenaktualisierungen.--x2, --y2: benutzerdefinierte Punktkoordinaten; erforderlich, wenn --point-constant custom verwendet wird.--eea-steps-json: JSON-Datei mit rekursiven Algorithmus-3-EEA-Zählungen.--allow-eea-n-mismatch: Nur-Debug-Überschreibung, die es erlaubt, dass das n der EEA-JSON vom angeforderten --n abweicht.--mcx-policy {clean-vchain,keep}: MCX-Expansionsrichtlinie für rekursives Zählen.--validate-full-mul: Für kleine n rekursives Zählen vollständiger Multiplikations-/Quadrierdefinitionen und Vergleich mit den zusammengesetzten Blockzählungen.--out: Pfad zur Ausgabe-JSON.Der Ausgabebericht enthält:
counting_mode
n
p
point_constant_kind
qiskit_width_report
eea_meta
block_summaries
raw_block_counters
key_ccx
validation
elapsed_s
Der Punktadditionszähler erstellt wiederverwendbare Qiskit-Schaltungen, zählt sie rekursiv in der {CCX, CX, X}-Basis und setzt dann größere wiederholte Blöcke wie Multiplikation, inverse Multiplikation, In-Place-Division, In-Place-Multiplikation, Square-minus und den gesamten Fig.14-Punktadditionsblock zusammen.
Dieses Repository enthält zwei einfache Python-Testtreiber. Sie wurden bewusst ohne pytest, Aer oder vollständige Zustandsvektorsimulation geschrieben. Die Tests erweitern Qiskit-Definitionen rekursiv, wo angemessen, und simulieren Rechenbasis-Zustände für Toffoli-Netzwerkblöcke.
Die EEA-Tests befinden sich in:
test_eea_strict_main.py
Führen Sie die standardmäßige EEA-Suite aus mit:
python test_eea_strict_main.py
Die Standardsuite überprüft:
n;3, 5, 7, 11, 13, 17, unter Verwendung sowohl exakter Schrittanzahlen als auch festgelegter T_max;3, 5, 7.Nützliche Varianten:
# Nur schnelle strukturelle + Blocktests.
python test_eea_strict_main.py --skip-endpoint --skip-alg1
# Den schwereren PDF/Table-4 p=37, x=13-Ablaufverfolgungsbenchmark einschließen.
python test_eea_strict_main.py --table4
# Alle x-Werte auch für Primzahlen über 13 testen.
python test_eea_strict_main.py --primes 3 5 7 11 13 17 --mid-all-x --verbose
Die Punktadditions-Tests befinden sich in:
test_point_addition_strict_main.py
Führen Sie die standardmäßige Punktadditions-Suite aus mit:
python test_point_addition_strict_main.py
Die standardmäßige Punktadditions-Suite überprüft:
n=256: 835 = 1 + 3*256 + 66;H, measure, reset, klassisch gesteuertem Z und swap-Operationen;Die Regressionsmatrix für große Primzahlen deckt repräsentative Paare der Feldbitbreite n und des Primzahlmoduls p ab, die von 12-Bit- bis 512-Bit-Primzahlfeldern reicht. Die getesteten Instanzen umfassen beispielsweise n=16, p=65521, n=32, p=4294967291, die secp256k1-Primzahl bei n=256 und repräsentative Primzahlen bei n=128, 160, 192, 224, 384, 512.
Für jedes (n,p)-Paar enthalten die Tests Grenz-, symmetrische, zufällige sowie relativ lange EEA-Ablaufverfolgungen. Die vollständige kompilierte Arithmetikassemblierung wird nur für ausgewählte Instanzen mittlerer Breite durchgeführt, während die größeren (n,p)-Paare zur Validierung des Schaltungsaufbaus, des Registerlayouts, der Zeitplanung und der rekursiven Ressourcenzählpfade verwendet werden.
Nützliche Varianten:
# Den winzigen integrierten Bericht überspringen und nur Konstruktion/Zeitplan/Assemblierung prüfen.
python test_point_addition_strict_main.py --skip-report
# Schneller Smoke-Test, der auch die Überprüfung der n=256-Breitenkonstruktion überspringt.
python test_point_addition_strict_main.py --skip-n256 --skip-report
# Eine andere kleine Primzahl/Breite für die kompilierte Blockvalidierung verwenden.
python test_point_addition_strict_main.py --n 5 --p 17
Wenn Qiskit nicht installiert ist, gibt test_point_addition_strict_main.py eine Überspringmeldung aus und wird erfolgreich beendet. Der EEA-Strenge-Test erfordert Qiskit, da er die EEA/PDF-Blockgatter erstellt.
Unser Paper berichtet numerische Ressourcenabschätzungsergebnisse für:
n = 64, 128, 160, 192, 224, 256, 384, 512
Ein typischer Workflow ist:
n aus.n aus.key_ccx, block_summaries und qiskit_width_report aus dem Ausgabebericht.Für große Breiten verwenden Sie --resume und behalten Sie die --workdir-Verzeichnisse, da Chunk- und Schritt-Checkpoints dazu dienen, unterbrochene lange Läufe zu unterstützen.
Wenn Sie diesen Codebestand in Ihrer Forschung verwenden, zitieren Sie bitte:
@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},
}