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.

Dimensione curva	Qubit standard	Qubit semiclassici	Risparmio	Verificato su hardware
4-bit (n=7)	11	5	55%	Sì
6-bit (n=31)	17	7	59%	Sì
7-bit (n=79)	26 + anc	14	46%	Sì
8-bit (n=139)	25 + anc	10 + anc	60%	No (overhead di sincronizzazione QPU)
10-bit (n=547)	31 + anc	12 + anc	61%	No (overhead di sincronizzazione QPU)