Algoritmo di Shor per ECDLP — Sottomissione al Q-Day Prize

Solutore quantistico per il problema del logaritmo discreto su curve ellittiche (ECDLP), costruito per la Q-Day Prize Challenge da Project Eleven. Obiettivo: recuperare le chiavi private ECC su hardware quantistico reale utilizzando l'algoritmo di Shor.

• Autore: Giancarlo Lelli
• Contatto: [email protected]
• LinkedIn: https://www.linkedin.com/in/giancarlolelli
• Background: Leader tecnologico con oltre 10 anni di esperienza in software enterprise, architettura full-stack e sviluppo cloud-native. Formazione in informatica con esperienza pratica negli ecosistemi .NET, Python, Rust e Cloud. Attualmente lavora come Cloud GTM Specialist focalizzato su architettura di soluzioni e ingegneria delle vendite.

Approccio

Tutte le curve della sfida utilizzano y^2 = x^3 + 7 su F_p (a = 0, b = 7), corrispondenti alla famiglia secp256k1. Il solutore implementa la variante a due registri dell'algoritmo di Shor per ECDLP:

1. Preparare i registri di conteggio |j>, |k> in sovrapposizione uniforme (Hadamard)
2. Calcolare |j>|k>|jG + kQ> tramite 2t addizioni di punto controllate (t = num_counting qubit)
3. Misurare il registro del punto, collassandolo su un qualche elemento di gruppo R
4. Applicare la QFT inversa ai registri di conteggio
5. Misurare j, k ed estrarre d dalla relazione j + kd = r (mod n)

La chiave privata d viene recuperata raccogliendo multipli campioni (j, k) che soddisfano la stessa relazione lineare modulo l'ordine del gruppo n. Il solutore supporta sei strategie di oracolo per le addizioni di punto controllate, selezionate automaticamente in base alla dimensione della curva o manualmente tramite --oracle.

Strategie di Oracolo

Strategia 1: Dense Unitary (predefinita per n_bits <= 6)

Utilizzata per curve con ordine di gruppo fino a ~6 bit. Implementata in projecteleven.py.

Ogni addizione di punto controllata "add S" è rappresentata come una matrice di permutazione 2^(n+1) x 2^(n+1) applicata tramite qc.unitary(). La matrice codifica l'azione completa del gruppo: il blocco in alto a sinistra è l'identità (controllo=0), il blocco in basso a destra permuta gli stati base secondo la mappa P -> P+S (controllo=1).

• Codifica: Indice del gruppo (0..n-1)
• Memoria: O(2^{2n}) per matrice
• Qubit: 2t + n (due registri di conteggio + registro del punto)
• Limitazione: La decomposizione unitaria di Qiskit è O(4^n), rendendo questo approccio impraticabile oltre ~6 bit

Strategia 2: Scomposizione Efficiente delle Permutazioni (predefinita per n_bits > 6)

Utilizzata per curve più grandi. Implementata in quantum_arithmetic.py.

Invece di costruire matrici dense, ogni permutazione "add S" viene scomposta in cicli di trasposizioni. Ogni trasposizione (scambio di due stati base |a> <-> |b>) viene implementata con:

1. Riduzione CNOT -- CNOT da un bit pivot a tutti gli altri bit differenti, riducendo la differenza multi-bit a una differenza a singolo bit
2. X multi-controllata -- Una porta MCX sul bit pivot, condizionata al fatto che tutti gli altri bit corrispondano al pattern target
3. Annullamento CNOT -- Passo inverso 1 per ripristinare i bit non pivot

L'MCX utilizza decomposizione a catena a V con (n-2) qubit ancilla dedicati, dando O(n) porte Toffoli per MCX invece di O(n^2) senza ancilla. Ogni addizione controllata viene costruita come un sottocircuito isolato e aggiunta come un singolo gate opaco, evitando la crescita quadratica del DAG in Qiskit.

• Codifica: Indice del gruppo (0..n-1)
• Memoria: O(N) per addizione (N = ordine del gruppo)
• Qubit: 2t + n + (n-2) ancilla
• Gate per addizione: O(N * n)

Strategia 3: Oracolo Quantistico Basato su Coordinate (--oracle coordinate)

Disponibile per curve fino a ~6 bit. Implementata in quantum_oracle.py.

Invece di codificare i punti come indici di gruppo, il registro quantistico contiene le coordinate (x, y) degli elementi del campo in binario più un flag di identità. La struttura del registro del punto è:

• x_reg: f_bits qubit (f_bits = ceil(log2(p)))
• y_reg: f_bits qubit
• id_flag: 1 qubit (1 = punto all'infinito)

Ogni "add S" controllata viene calcolata dalla formula di addizione EC su tutte le codifiche valide delle coordinate, producendo una permutazione sul registro delle coordinate. Questa permutazione viene scomposta in cicli di trasposizioni utilizzando la stessa infrastruttura di riduzione CNOT + MCX della Strategia 2.

• Codifica: Coordinate (x, y, id_flag)
• Qubit: 2t + 2f_bits + 1 + max(0, 2f_bits - 1) ancilla
• Gate per addizione: O(N * f_bits)

Strategia 4: Oracolo Aritmetico (--oracle arithmetic)

Struttura per addizione di punto a scala polinomiale. Implementata in quantum_oracle.py e quantum_arithmetic.py.

Utilizza la codifica delle coordinate (come la Strategia 3) con primitive aritmetiche modulari basate su QFT come blocchi costitutivi verso un'addizione di punto completamente aritmetica. Il codice include implementazioni testate di:

• Addizionatore modulare di Beauregard -- basato su QFT (target + costante) mod p con corretto discomputo delle ancilla
• Moltiplicazione modulare quantistico-quantistica -- |a>|b>|0> -> |a>|b>|a*b mod p> tramite shift-and-add con raddoppio modulare esplicito, O(n^3) gate
• Permutazione di inversione modulare -- |x> -> |x^{-1} mod p> tramite trasposizioni di tabella di ricerca
• Addizione modulare quantistico-quantistica controllata -- |a> controllato -> |a + b mod p> con riduzione di Beauregard

Le primitive aritmetiche raggiungono una scala O(n^3) per addizione di punto rispetto a O(N*n) per l'approccio a permutazione. Tuttavia, le operazioni basate su QFT hanno un fattore costante circa 150x più grande, rendendo l'approccio aritmetico più efficiente solo per curve con ordine di gruppo sopra ~20 bit. Per le dimensioni attuali della sfida (fino a 12 bit), l'addizionatore basato su permutazioni rimane più veloce e viene utilizzato per impostazione predefinita.

Strategia 5: Stima di Fase Semiclassica di Google (--oracle google)

Implementata in google_semiclassical.py. Ispirata dalla tecnica di stima di fase a qubit riciclato di Griffiths & Niu (1996), applicata su larga scala in Babbush et al. (2026) per le stime delle risorse ECDLP secp256k1. L'articolo di Babbush et al. è stato pubblicato il 30 marzo 2026.

Sostituisce i due registri di conteggio multi-qubit (j, k) e la QFT inversa bulk con due singoli qubit riciclati e correzioni di fase condizionate classicamente. Ogni bit del registro di conteggio viene elaborato sequenzialmente: preparare in |+>, applicare addizione di punto controllata, correggere la fase in base a tutti i bit misurati in precedenza, quindi misurare. Le primitive di circuito dinamico reset + if_test in Qiskit consentono questo su hardware IBM Quantum.

L'oracolo per le addizioni di punto controllate è delegato all'infrastruttura esistente (unitaria densa per <= 6 bit, permutazione efficiente per > 6 bit), quindi il risparmio di qubit deriva interamente dall'eliminazione dei registri di conteggio.

• Codifica: Come la strategia sottostante (indice del gruppo)
• Qubit: 2 + n_bits + ancilla (vs 2t + n_bits + ancilla)
• Compromesso: Richiede circuiti dinamici (misurazione a metà circuito, reset, gate condizionati classicamente). Funziona su IBM Heron r2 fino a 7 bit; a partire da 8 bit l'overhead di sincronizzazione del feedback classico supera il budget temporale della QPU

Strategia 6: Addizione Modulare Ripple-Carry (--oracle ripple)

Implementata in ripple_carry_shor.py. Utilizza addizionatori ripple-carry CDKM (Cuccaro et al. 2004) per le addizioni di punto controllate, sostituendo sia le matrici unitarie dense che i circuiti di trasposizione scomposti in cicli.

Nella codifica con indice di gruppo, il punto P = kG è rappresentato dal suo indice k nel gruppo ciclico. Aggiungere S = sG diventa addizione modulare della costante classica s (mod n). L'intuizione chiave: ogni addizione di punto controllata si riduce a una singola addizione modulare controllata di una costante nota, implementata tramite CDKMRippleCarryAdder e IntegerComparator di Qiskit.

L'oracolo consiste di 2m addizioni modulari controllate (m per registro di conteggio), dove ogni add-mod controllata esegue:

1. Caricare la costante nel registro ancilla tramite CX dal qubit di controllo
2. Half-adder CDKM per aggiungere l'ancilla all'accumulatore (solo gate nearest-neighbor)
3. Comparatore intero per rilevare overflow (acc >= n)
4. Sottrazione condizionale di n tramite addizione controllata da flag di 2^m1 - n
5. Discomputo del flag tramite probing basato su carry

Nella costruzione del circuito non viene utilizzata alcuna conoscenza della chiave privata d. Gli indici di gruppo per le potenze di G sono calcolati come 2^i mod n (pubblici). Gli indici di gruppo per le potenze di Q sono derivati dall'enumerazione pubblica del gruppo ciclico generato da G — il punto Q viene cercato in questa enumerazione.

• Codifica: Indice del gruppo (0..n-1)
• Qubit: 4m + 5 dove m = ceil(log2(n))
• Gate per addizione: Operazioni CDKM O(m), ciascuna con O(m) gate CX
• Scala CX totale: O(m^3)
• Mappatura hardware: CDKM utilizza solo gate nearest-neighbor, dando un overhead di routing ~1x sulla topologia heavy-hex di IBM (vs 26-33x per gli addizionatori basati su QFT)

Confronto

Primitive Aritmetiche QFT

Il codice include blocchi costitutivi aritmetici modulari basati su QFT (addizionatori Beauregard/Draper, moltiplicazione modulare quantistico-quantistica, inversione/negazione modulare) come fondamento per una codifica delle coordinate completamente aritmetica a 256 bit. Queste primitive sono state verificate corrette tramite simulazione Statevector per primi fino a p=13.

Risultati

Chiavi private recuperate con successo su hardware IBM Quantum per curve della sfida fino a 17 bit:

Tutte le esecuzioni sono state effettuate sul piano open-instance di IBM Quantum, che concede 10 minuti di calcolo quantistico gratuito al mese. I log di esecuzione completi sono nella cartella executions/.

La strategia ripple-carry (Strategia 6) ha permesso un salto importante: da 10 bit (40 qubit, 2M gate) a 17 bit (69 qubit, 112K gate) — un aumento di 7 bit nella dimensione della chiave con una riduzione di 18x nel conteggio di gate a due qubit. La struttura di gate nearest-neighbor dell'addizionatore CDKM si mappa efficientemente sulla topologia heavy-hex di IBM, mantenendo l'overhead di routing vicino a 1x.

Stima di Fase Semiclassica: Circuiti Dinamici su Hardware IBM

La strategia semiclassica (--oracle google) ha recuperato con successo chiavi a 4 bit, 6 bit e 7 bit utilizzando circuiti dinamici (reset a metà circuito, gate p condizionati classicamente tramite if_test) su processori IBM Heron r2. A 7 bit, il circuito utilizza solo 14 qubit (vs 26 per l'approccio a permutazione standard) producendo conteggi di gate a 2 qubit comparabili dopo la transpilazione.

A partire da 8 bit, l'approccio semiclassico diventa impraticabile sull'attuale hardware IBM. Sebbene if_else e reset siano supportati su Heron r2 (confermato tramite ispezione del target del backend), ogni punto di feedback classico richiede una sincronizzazione completa della QPU — tutti i 156 qubit fisici devono rimanere inattivi mentre il controller classico elabora il condizionale per i ~16 qubit attivi. Con ~295K gate CZ suddivisi in 16+ punti di feedback, l'overhead di esecuzione per singolo tiro fa superare il budget temporale della QPU. L'approccio a permutazione standard, che esegue lo stesso conteggio di gate in un unico lotto continuo senza circuiti dinamici, completa con successo a questa scala.

Una troncatura approssimativa della QFT (parametro max_corrections) riduce il numero di blocchi if_else da O(n^2) a O(n) mantenendo solo le k correzioni di fase più vicine per passo di misurazione (angoli oltre k contribuiscono < pi/2^{k+1}, al di sotto del rumore hardware). Con max_corrections=1, il circuito a 8 bit ha 16 blocchi if_else — ancora sufficienti a causare timeout su hardware IBM a questo conteggio di gate.

Analisi del Rumore e della Fedeltà

Fedeltà Stimata del Circuito

Assumendo una fedeltà tipica del gate a due qubit (CX) di IBM Quantum di circa il 99.5%, la fedeltà stimata del circuito diminuisce esponenzialmente con il conteggio dei gate:

La fedeltà del circuito è calcolata come F ≈ (0.995)^{CX_count}. Per tutto oltre i 4 bit, la fedeltà stimata è astronomicamente piccola — la distribuzione di output è schiacciantemente rumore.

Perché Funziona Ancora

Per 8 bit e superiori, ogni tiro produce una stringa di bit quasi unica (8.128 risultati unici su 8.192 tiri a 8 bit; tutti i 20.000 unici a 16 e 17 bit). L'output è indistinguibile da un campionamento casuale uniforme a livello di stringa di bit. Tuttavia, l'algoritmo recupera ancora la chiave privata corretta.

L'intuizione chiave è che la post-elaborazione di Shor è robusta al rumore in un modo che l'analisi grezza delle stringhe di bit non lo è. Ogni tiro produce una tripla di misurazione (j, k, r). L'estrazione calcola d_cand = (r - j) · k^{-1} mod n e verifica tramite d_cand · G == Q. Solo il vero d supera la verifica EC, quindi anche un singolo candidato corretto tra migliaia di tiri rumorosi è sufficiente.

Una tripla puramente casuale (j, k, r) produce il d_cand corretto con probabilità ~1/n. Con S tiri, il numero atteso di hit verificati dal solo rumore è ~S/n. A 17 bit (n=65.173, S=20.000), ciò dà ~0.3 hit attesi dal rumore — qualsiasi recupero riuscito a questa scala fornisce evidenza di un segnale quantistico oltre il rumore classico.

Per le curve più piccole dove i tiri >> n (es. 10-bit con n=547 e 1.024 tiri), il rumore di fondo è ~1.024/547 ≈ 1.9 voti per candidato. Anche una manciata di tiri portatori di segnale spinge il d corretto sopra il rumore di fondo. Questo spiega come l'algoritmo abbia successo nonostante fedeltà del circuito che sembrerebbero rendere il calcolo impossibile.

Segnale Quantistico vs Rumore Classico

A scala giocattolo, il passo di verifica dell'estrazione (d_cand * G == Q) funge da filtro che accetta solo il vero d. Ciò significa che anche triple puramente casuali (j, k, r) produrranno candidati validi a un tasso di circa shots / n per esecuzione. Quando shots >> n, il rumore casuale da solo può recuperare d con alta probabilità.

Per testare se il circuito quantistico contribuisce con segnale oltre questo rumore di fondo classico, abbiamo eseguito la sfida a 6 bit (n=31) con solo 8 tiri (ben al di sotto dell'ordine del gruppo) 10 volte su ibm_kingston:

Risultato: 4/10 successi (40%) vs un rumore di fondo classico di circa il 20% (calcolato tramite simulazione Monte Carlo: 8 stringhe di bit casuali con (r-j)*k_inv mod 31 filtrate tramite verifica). Test binomiale a una coda: P(X >= 4 | n=10, p=0.20) = 0.121, indicando un miglioramento di 2x rispetto al rumore di fondo. Sebbene non individualmente statisticamente significativo a p < 0.05 (che avrebbe richiesto 5+ successi), il tasso osservato è coerente con un segnale quantistico che contribuisce circa 1-2 coppie (j, k) valide aggiuntive per esecuzione oltre quanto il caso casuale fornisce.

Questo risultato si colloca tra il rumore di fondo classico e il regime teorico di vantaggio quantistico. A dimensioni di curva maggiori dove n >> shots, il rumore di fondo scende sotto l'1% e qualsiasi recupero riuscito della chiave diventa una forte evidenza di computazione quantistica.

Quick Start```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

### Come eseguire

Hai bisogno di un account [IBM Quantum](https://quantum.ibm.com/). Passa il tuo token API durante la prima esecuzione e verrà salvato localmente:```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

Opzioni CLI

Struttura del Progetto```

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

## Riferimenti

- P. Shor, ["Algoritmi per il calcolo quantistico: logaritmi discreti e fattorizzazione"](https://arxiv.org/abs/quant-ph/9508027) (1994)
- S. Beauregard, ["Circuito per l'algoritmo di Shor che utilizza 2n+3 qubit"](https://arxiv.org/abs/quant-ph/0205095) (2003)
- S. A. Cuccaro, T. G. Draper, S. A. Kutin, D. P. Moulton, ["Un nuovo circuito di addizione quantistica ripple-carry"](https://arxiv.org/abs/quant-ph/0410184) (2004)
- M. Roetteler, M. Naehrig, K. Svore, K. Lauter, ["Stime delle risorse quantistiche per il calcolo di logaritmi discreti su curve ellittiche"](https://arxiv.org/abs/1706.06752) (2017)
- R. Griffiths, C.-S. Niu, ["Trasformata di Fourier semiclassica per il calcolo quantistico"](https://arxiv.org/abs/quant-ph/9511007) (1996)
- R. Babbush et al., ["Proteggere le criptovalute a curve ellittiche dalle vulnerabilità quantistiche: stime delle risorse e mitigazioni"](https://quantumai.google/static/site-assets/downloads/cryptocurrency-whitepaper.pdf) (2026)

## Licenza

Questo progetto è un invio alla Q-Day Prize Challenge rilasciato sotto [MIT LICENSE](https://github.com/yuvadm/quantumslop/blob/HEAD/LICENSE)