Algorithme de Shor pour l'ECDLP — Soumission au Q-Day Prize

Solveur quantique pour le problème du logarithme discret sur courbe elliptique (ECDLP), construit pour le Q-Day Prize Challenge par Project Eleven. L'objectif : récupérer des clés privées ECC sur du matériel quantique réel en utilisant l'algorithme de Shor.

• Auteur : Giancarlo Lelli
• Contact : [email protected]
• LinkedIn : https://www.linkedin.com/in/giancarlolelli
• Parcours : Leader technologique avec plus de 10 ans d'expérience dans les logiciels d'entreprise, l'architecture full-stack et le développement cloud-native. Formation en informatique avec une expérience pratique dans les écosystèmes .NET, Python, Rust et Cloud. Travaille actuellement en tant que spécialiste GTM Cloud, axé sur l'architecture de solutions et l'ingénierie commerciale.

Approche

Toutes les courbes du défi utilisent y^2 = x^3 + 7 sur F_p (a = 0, b = 7), correspondant à la famille secp256k1. Le solveur implémente la variante à deux registres de l'algorithme de Shor pour l'ECDLP :

1. Préparer les registres de comptage |j>, |k> en superposition uniforme (Hadamard)
2. Calculer |j>|k>|jG + kQ> via 2t additions de points contrôlées (t = num_counting qubits)
3. Mesurer le registre de points, le réduisant à un élément de groupe R
4. Appliquer la QFT inverse aux registres de comptage
5. Mesurer j, k et extraire d à partir de la relation j + kd = r (mod n)

La clé privée d est récupérée en collectant plusieurs échantillons (j, k) qui satisfont la même relation linéaire modulo l'ordre du groupe n. Le solveur prend en charge six stratégies d'oracle pour les additions de points contrôlées, sélectionnées automatiquement en fonction de la taille de la courbe ou manuellement via --oracle.

Stratégies d'Oracle

Stratégie 1 : Unitaire dense (par défaut pour n_bits <= 6)

Utilisée pour les courbes avec un ordre de groupe jusqu'à ~6 bits. Implémentée dans projecteleven.py.

Chaque addition de point contrôlée "add S" est représentée comme une matrice de permutation 2^(n+1) x 2^(n+1) appliquée via qc.unitary(). La matrice encode l'action complète du groupe : le bloc supérieur gauche est l'identité (contrôle=0), le bloc inférieur droit permute les états de base selon l'application P -> P+S (contrôle=1).

• Encodage : Indice de groupe (0..n-1)
• Mémoire : O(2^{2n}) par matrice
• Qubits : 2t + n (deux registres de comptage + registre de points)
• Limitation : La décomposition unitaire de Qiskit est O(4^n), ce qui rend cette approche irréalisable au-delà de ~6 bits

Stratégie 2 : Décomposition de permutation efficace (par défaut pour n_bits > 6)

Utilisée pour les courbes plus grandes. Implémentée dans quantum_arithmetic.py.

Au lieu de construire des matrices denses, chaque permutation "add S" est décomposée en cycles, puis en transpositions. Chaque transposition (échange de deux états de base |a> <-> |b>) est implémentée avec :

1. Réduction CNOT — Des CNOT d'un bit pivot vers tous les autres bits différents, réduisant la différence multi-bit à une différence d'un seul bit
2. X multi-contrôlé — Une porte MCX sur le bit pivot, conditionnée par le fait que tous les autres bits correspondent au motif cible
3. Annulation des CNOT — Inverser l'étape 1 pour restaurer les bits non-pivot

Le MCX utilise une décomposition en chaîne en V avec (n-2) qubits ancilla dédiés, donnant O(n) portes Toffoli par MCX au lieu de O(n^2) sans ancillas. Chaque addition contrôlée est construite comme un sous-circuit isolé et ajoutée comme une porte opaque unique, évitant une croissance quadratique du DAG dans Qiskit.

• Encodage : Indice de groupe (0..n-1)
• Mémoire : O(N) par addition (N = ordre du groupe)
• Qubits : 2t + n + (n-2) ancillas
• Portes par addition : O(N * n)

Stratégie 3 : Oracle quantique basé sur les coordonnées (--oracle coordinate)

Disponible pour les courbes jusqu'à ~6 bits. Implémentée dans quantum_oracle.py.

Au lieu d'encoder les points comme des indices de groupe, le registre quantique contient les coordonnées de champ (x, y) réelles en binaire plus un indicateur d'identité. La disposition du registre de points est :

• x_reg : f_bits qubits (f_bits = ceil(log2(p)))
• y_reg : f_bits qubits
• id_flag : 1 qubit (1 = point à l'infini)

Chaque "add S" contrôlé est calculé à partir de la formule d'addition EC sur tous les encodages de coordonnées valides, produisant une permutation sur le registre de coordonnées. Cette permutation est décomposée en cycles puis en transpositions en utilisant la même infrastructure de réduction CNOT + MCX que la Stratégie 2.

• Encodage : Coordonnées (x, y, id_flag)
• Qubits : 2t + 2f_bits + 1 + max(0, 2f_bits - 1) ancillas
• Portes par addition : O(N * f_bits)

Stratégie 4 : Oracle arithmétique (--oracle arithmetic)

Cadre pour l'addition de points à mise à l'échelle polynomiale. Implémentée dans quantum_oracle.py et quantum_arithmetic.py.

Utilise l'encodage par coordonnées (identique à la Stratégie 3) avec des primitives arithmétiques modulaires basées sur la QFT comme éléments de base pour l'addition de points entièrement arithmétique. La base de code comprend des implémentations testées de :

• Additionneur modulaire de Beauregard — basé sur la QFT (cible + constante) mod p avec désinformatisation appropriée des ancillas
• Multiplication modulaire quantique-quantique — |a>|b>|0> -> |a>|b>|a*b mod p> par décalage et addition avec doublement modulaire explicite, O(n^3) portes
• Permutation d'inverse modulaire — |x> -> |x^{-1} mod p> par transpositions de table de correspondance
• Addition modulaire quantique-quantique contrôlée — |a> contrôlé -> |a + b mod p> avec réduction de Beauregard

Les primitives arithmétiques atteignent une mise à l'échelle O(n^3) par addition de point contre O(N*n) pour l'approche par permutation. Cependant, les opérations basées sur la QFT ont un facteur constant environ 150 fois plus grand, rendant l'approche arithmétique plus efficace uniquement pour les courbes au-delà de ~20 bits d'ordre de groupe. Pour les tailles de défi actuelles (jusqu'à 12 bits), l'additionneur par permutation reste plus rapide et est utilisé par défaut.

Stratégie 5 : Estimation de phase semi-classique de Google (--oracle google)

Implémentée dans google_semiclassical.py. Inspirée de la technique d'estimation de phase à recyclage de qubits de Griffiths & Niu (1996), appliquée à grande échelle dans Babbush et al. (2026) pour les estimations de ressources ECDLP secp256k1. L'article de Babbush et al. a été publié le 30 mars 2026.

Remplace les deux registres de comptage multi-qubits (j, k) et la QFT inverse globale par deux qubits recyclés uniques et des corrections de phase conditionnées classiquement. Chaque bit du registre de comptage est traité séquentiellement : préparer en |+>, appliquer l'addition de point contrôlée, corriger la phase en fonction de tous les bits précédemment mesurés, puis mesurer. Les primitives de circuit dynamique reset + if_test dans Qiskit permettent cela sur le matériel IBM Quantum.

L'oracle pour les additions de points contrôlées est délégué à l'infrastructure existante (unitaire dense pour <= 6 bits, permutation efficace pour > 6 bits), donc les économies de qubits proviennent entièrement de la suppression des registres de comptage.

• Encodage : Identique à la stratégie sous-jacente (indice de groupe)
• Qubits : 2 + n_bits + ancillas (vs 2t + n_bits + ancillas)
• Compromis : Nécessite des circuits dynamiques (mesure en cours de circuit, reset, portes conditionnées classiquement). Fonctionne sur IBM Heron r2 jusqu'à 7 bits ; à 8 bits et plus, la surcharge de synchronisation du retour classique dépasse le budget de temps QPU

Stratégie 6 : Addition modulaire à propagation de retenue (--oracle ripple)

Implémentée dans ripple_carry_shor.py. Utilise des additionneurs à propagation de retenue CDKM (Cuccaro et al. 2004) pour les additions de points contrôlées, remplaçant à la fois les matrices unitaires denses et les circuits de transposition décomposés en cycles.

Dans l'encodage par indice de groupe, le point P = kG est représenté par son indice k dans le groupe cyclique. Ajouter S = sG devient une addition modulaire de la constante classique s (mod n). L'idée clé : chaque addition de point contrôlée se réduit à une unique addition modulaire contrôlée d'une constante connue, implémentée via CDKMRippleCarryAdder et IntegerComparator de Qiskit.

L'oracle consiste en 2m additions modulaires contrôlées (m par registre de comptage), où chaque addition modulaire contrôlée effectue :

1. Charger la constante dans le registre ancilla via CX à partir du qubit de contrôle
2. Demi-additionneur CDKM pour ajouter l'ancilla dans l'accumulateur (portes uniquement voisines les plus proches)
3. Comparateur entier pour détecter le débordement (acc >= n)
4. Soustraction conditionnelle de n via l'addition contrôlée par indicateur de 2^m1 - n
5. Désinformatisation de l'indicateur via sondage basé sur la retenue

Aucune connaissance de la clé privée d n'est utilisée dans la construction du circuit. Les indices de groupe pour les puissances de G sont calculés comme 2^i mod n (publics). Les indices de groupe pour les puissances de Q sont dérivés de l'énumération publique du groupe cyclique généré par G — le point Q est recherché dans cette énumération.

• Encodage : Indice de groupe (0..n-1)
• Qubits : 4m + 5 où m = ceil(log2(n))
• Portes par addition : Opérations CDKM O(m), chacune avec O(m) portes CX
• Mise à l'échelle CX totale : O(m^3)
• Mapping matériel : CDKM utilise uniquement des portes voisines les plus proches, donnant une surcharge de routage d'environ 1x sur la topologie heavy-hex d'IBM (contre 26-33x pour les additionneurs basés sur QFT)

Comparaison

Primitives arithmétiques QFT

La base de code inclut des blocs de construction arithmétiques modulaires basés sur la QFT (additionneurs Beauregard/Draper, multiplication modulaire quantique-quantique, inverse/négation modulaire) en tant que base vers un encodage par coordonnées entièrement arithmétique à 256 bits. Ces primitives ont été vérifiées correctes via simulation Statevector pour des nombres premiers jusqu'à p=13.

Résultats

Clés privées récupérées avec succès sur du matériel quantique IBM pour des courbes du défi jusqu'à 17 bits :

Toutes les exécutions ont été effectuées sur le plan open-instance d'IBM Quantum, qui accorde 10 minutes de calcul quantique gratuit par mois. Les journaux d'exécution complets se trouvent dans le dossier executions/.

La stratégie de propagation de retenue (Stratégie 6) a permis un bond majeur : de 10 bits (40 qubits, 2M portes) à 17 bits (69 qubits, 112K portes) — une augmentation de 7 bits de la taille de clé avec une réduction de 18x du nombre de portes deux-qubits. La structure de portes voisines les plus proches de l'additionneur CDKM se mappe efficacement sur la topologie heavy-hex d'IBM, maintenant la surcharge de routage près de 1x.

PE semi-classique : Circuits dynamiques sur matériel IBM

La stratégie semi-classique (--oracle google) a récupéré avec succès des clés à 4, 6 et 7 bits en utilisant des circuits dynamiques (reset en cours de circuit, portes p conditionnées classiquement via if_test) sur les processeurs IBM Heron r2. À 7 bits, le circuit n'utilise que 14 qubits (contre 26 pour l'approche par permutation standard) tout en produisant des nombres de portes 2Q comparables après transpilation.

À 8 bits et au-delà, l'approche semi-classique devient impraticable sur le matériel IBM actuel. Bien que if_else et reset soient supportés sur Heron r2 (confirmé par inspection de la cible du backend), chaque point de retour classique nécessite une synchronisation complète du QPU — les 156 qubits physiques doivent être inactifs pendant que le contrôleur classique traite le conditionnel pour les ~16 qubits actifs. Avec ~295K portes CZ réparties sur 16+ points de retour, la surcharge d'exécution par shot dépasse le budget de temps QPU. L'approche par permutation standard, qui exécute le même nombre de portes en un seul lot continu sans circuits dynamiques, se termine avec succès à cette échelle.

Une troncature approximative de la QFT (paramètre max_corrections) réduit le nombre de blocs if_else de O(n^2) à O(n) en ne conservant que les k corrections de phase les plus proches par étape de mesure (les angles au-delà de k contribuent < pi/2^{k+1}, en dessous du plancher de bruit matériel). Avec max_corrections=1, le circuit 8 bits a 16 blocs if_else — encore suffisant pour provoquer un dépassement de temps sur le matériel IBM à ce nombre de portes.

Analyse du bruit et de la fidélité

Fidélité estimée du circuit

En supposant une fidélité typique de porte deux-qubits (CX) IBM Quantum d'environ 99,5 %, la fidélité estimée du circuit décroît exponentiellement avec le nombre de portes :

La fidélité du circuit est calculée comme F ≈ (0,995)^{CX_count}. Au-delà de 4 bits, la fidélité estimée est astronomiquement faible — la distribution de sortie est massivement dominée par le bruit.

Pourquoi cela fonctionne quand même

Pour 8 bits et plus, chaque shot produit un bitstring quasi unique (8 128 résultats uniques sur 8 192 shots à 8 bits ; les 20 000 uniques à 16 et 17 bits). La sortie est indiscernable d'un échantillonnage aléatoire uniforme au niveau du bitstring. Pourtant, l'algorithme récupère toujours la clé privée correcte.

L'idée clé est que le post-traitement de Shor est robuste au bruit d'une manière que l'analyse brute des bitstrings ne l'est pas. Chaque shot produit un triplet de mesure (j, k, r). L'extraction calcule d_cand = (r - j) · k^{-1} mod n et vérifie via d_cand · G == Q. Seul le vrai d passe la vérification EC, donc même un seul candidat correct parmi des milliers de shots bruités suffit.

Un triplet (j, k, r) purement aléatoire produit le d_cand correct avec une probabilité d'environ 1/n. Avec S shots, le nombre attendu de coups vérifiés provenant uniquement du bruit est d'environ S/n. À 17 bits (n=65 173, S=20 000), cela donne environ 0,3 coup de bruit attendu — toute récupération réussie à cette échelle fournit une preuve de signal quantique au-delà du plancher de bruit classique.

Pour les courbes plus petites où shots >> n (par exemple, 10 bits avec n=547 et 1 024 shots), le plancher de bruit est d'environ 1 024/547 ≈ 1,9 votes par candidat. Même une poignée de shots porteurs de signal pousse le d correct au-dessus du plancher de bruit. Cela explique comment l'algorithme réussit malgré des fidélités de circuit qui sembleraient rendre le calcul impossible.

Signal quantique vs bruit classique

À l'échelle de jouet, l'étape de vérification de l'extraction (d_cand * G == Q) agit comme un filtre qui n'accepte que le vrai d. Cela signifie que même des triplets (j, k, r) purement aléatoires produiront des candidats valides à un taux d'environ shots / n par exécution. Lorsque shots >> n, le bruit aléatoire seul peut récupérer d avec une probabilité élevée.

Pour tester si le circuit quantique contribue un signal au-delà de ce plancher de bruit classique, nous avons exécuté le défi 6 bits (n=31) avec seulement 8 shots (bien en dessous de l'ordre du groupe) 10 fois sur ibm_kingston :

Résultat : 4/10 succès (40 %) contre une ligne de base de bruit classique d'environ 20 % (calculée par simulation Monte Carlo : 8 bitstrings aléatoires avec (r-j)*k_inv mod 31 filtrés par vérification). Test binomial unilatéral : P(X >= 4 | n=10, p=0,20) = 0,121, indiquant une amélioration de 2x par rapport au plancher de bruit. Bien que non statistiquement significatif individuellement à p < 0,05 (ce qui nécessiterait 5+ succès), le taux observé est cohérent avec un signal quantique contribuant environ 1-2 paires (j, k) valides supplémentaires par exécution par rapport à ce que le hasard fournirait.

Ce résultat se situe entre le plancher de bruit classique et le régime d'avantage quantique théorique. Pour des tailles de courbe plus grandes où n >> shots, la ligne de base de bruit tombe en dessous de 1 % et toute récupération réussie de clé devient une preuve solide de calcul quantique.

Démarrage Rapide```bash

git clone https://github.com/GiancarloLelli/quantum.git cd quantum

python -m venv . Scripts\Activate.ps1 # For Windows only

pip install -r requirements.txt

### Comment exécuter

Vous avez besoin d'un compte [IBM Quantum](https://quantum.ibm.com/). Passez votre jeton API lors de la première exécution et il sera sauvegardé localement :```bash
# Solve the 4-bit challenge curve:
python projecteleven.py --challenge 4 --token YOUR_IBM_TOKEN --backend ibm_marrakesh

# Subsequent runs (token already saved):
python projecteleven.py --challenge 4 --backend ibm_marrakesh

# Use the coordinate-based quantum oracle:
python projecteleven.py --challenge 4 --oracle coordinate --backend ibm_marrakesh

# Use the arithmetic oracle (coordinate encoding + QFT primitives):
python projecteleven.py --challenge 4 --oracle arithmetic --backend ibm_marrakesh

# Use ripple-carry modular addition (CDKM — best for 8-bit+):
python projecteleven.py --challenge 16 --oracle ripple --backend ibm_fez --shots 20000

# Use Google semiclassical phase estimation (qubit-recycled):
python projecteleven.py --challenge 4 --oracle google --backend ibm_marrakesh

# Use a specific IBM Quantum instance:
python projecteleven.py --challenge 4 --instance ibm-q/open/main --backend ibm_marrakesh

# Verify curve parameters without quantum execution:
python projecteleven.py --curve curve_4 --verify-only

CLI Options

Structure du projet```

projecteleven.py # Shor solver — dense unitary approach + CLI entry point quantum_arithmetic.py # Efficient permutation decomposition + QFT arithmetic primitives quantum_oracle.py # Coordinate-based oracle + arithmetic oracle framework google_semiclassical.py # Google semiclassical PE — qubit-recycled phase estimation ripple_carry_shor.py # Ripple-carry modular addition oracle (CDKM) — best for 8-bit+ input_curves.json # Challenge curves (4-bit to 30-bit) problem/curves.py # Curve generation utility requirements.txt # qiskit, qiskit-ibm-runtime

## Références

- P. Shor, ["Algorithmes pour le calcul quantique : logarithmes discrets et factorisation"](https://arxiv.org/abs/quant-ph/9508027) (1994)
- S. Beauregard, ["Circuit pour l'algorithme de Shor utilisant 2n+3 qubits"](https://arxiv.org/abs/quant-ph/0205095) (2003)
- S. A. Cuccaro, T. G. Draper, S. A. Kutin, D. P. Moulton, ["Un nouveau circuit d'addition par ripple-carry quantique"](https://arxiv.org/abs/quant-ph/0410184) (2004)
- M. Roetteler, M. Naehrig, K. Svore, K. Lauter, ["Estimations de ressources quantiques pour le calcul de logarithmes discrets sur courbes elliptiques"](https://arxiv.org/abs/1706.06752) (2017)
- R. Griffiths, C.-S. Niu, ["Transformée de Fourier semi-classique pour le calcul quantique"](https://arxiv.org/abs/quant-ph/9511007) (1996)
- R. Babbush et al., ["Sécuriser les cryptomonnaies à courbe elliptique contre les vulnérabilités quantiques : estimations de ressources et atténuations"](https://quantumai.google/static/site-assets/downloads/cryptocurrency-whitepaper.pdf) (2026)

## Licence

Ce projet est une soumission au Q-Day Prize Challenge publié sous [MIT LICENSE](https://github.com/giancarlolelli/quantum/blob/HEAD/LICENSE)