Algoritmo di Shor
Introduzione: parliamo di numeri primi...
La sicurezza di algoritmi di crittografia quali l'RSA è garantita dalla difficoltà computazionale di scomporre un numero molto grande nei suoi fattori primi.
Facciamo un esempio pratico: dati i numeri (primi) 35747 e 59123, calcolare il loro prodotto
35747 × 59123 = 2113469881
è un'operazione relativamente semplice (dal punto di vista computazionale richiede un numero di passaggi che dipende in maniera polinomiale dal numero di cifre che compongono l'input).
L'operazione inversa, ossia partire dal numero 2113469881 ed ottenere i suoi fattori, non è altrettanto semplice: semplificando, si può affermare che l'unico modo per stabilire se un certo numero sia primo o meno, sia quello di dividerlo per tutti i numeri primi (compresi tra 1 e la radice del numero stesso) fino a che se ne trova (eventualmente) uno che ci stia un numero intero di volte.
La complessità di questo procedimento, però, è di tipo esponenziale, ossia il numero di operazioni da effettuare (e, dunque, il tempo necessario per il calcolo) aumenta molto velocemente rispetto al numero di cifre del numero in ingresso.
Teorema. Il problema di fattorizzare il numero N, può essere ricondotto a quello di determinare il periodo minimo p della seguente funzione:
fa, N(x) = ax mod N
dove a deve essere co-primo con N. La funzione a "mod" b indica il resto della divisione intera tra a e b.
Si ha, in generale, che fa, N(x) è periodica, con periodo minimo p. Inoltre, se p è pari e se p mod N è diverso da N - 1, i fattori primi di cui N è il prodotto sono:
MCD(ap/2 - 1, N) e MCD(ap/2 +1, N)
Osservazione: trovare il Massimo Comun Divisore di due numeri è un problema che ha come soluzione un algoritmo (detto di Euclide) a complessità polinomiale!
In definitiva, la complessità del problema (polinomiale o esponenziale) è determinata da quella dell'algoritmo usato per trovare p. Classicamente, anche se nessuno è riuscito a dimostrare che questo sia un problema NP, tutti gli algoritmi noti per risolvere il problema sono a complessità esponenziale.
Esempio pratico: consideriamo N = 15 e scegliamo a = 7. Si ha:
| x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | … |
| 7x mod 15 | 1 | 7 | 4 | 13 | 1 | 7 | 4 | … |
Si può osservare che la funzione risulta periodica con periodo p = 4, per cui i due fattori sono:
| 74/2 - 1 = 48 | → | MCD(48, 15) = 3 |
| 74/2 + 1 = 50 | → | MCD(50, 15) = 5 |
Algoritmi quantistici di ricerca
TODO.
Dunque, cosa cambierebbe con i computer quantistici?
L'algoritmo di Shor trasformerebbe radicalmente tutta la situazione riducendo la complessità del problema da esponenziale (meglio dire non polinomiale) a polinomiale. L'unico dettaglio è che esso sfrutta le proprietà della "computazione quantistica" e, dunque, potrebbe funzionare solo in un computer quantistico.
L'applicazione più immediata di questo algoritmo, consisterebbe nella decifrazione di dati crittografati con l'algoritmo RSA (o altri analoghi in cui, nella fase di cifratura, entrano in gioco i prodotti tra grandi numeri).
Il problema pratico, non trascurabile, è che per scomporre numeri della lunghezza tipica delle chiavi RSA bisognerebbe realizzare un apparato in grado di preparare, gestire e mantenere stabile per il tempo del calcolo circa venti-trentamila q-bits. Tuttavia, è possibile migliorare questo sistema (ad esempio applicando l'algoritmo di ricerca di Grover) in modo da abbassare il numero di q-bit necessari a circa duemila.
Per ora, il circuito necessario per implementare l'algoritmo di Shor è stato realizzato sperimentalmente, ma con pochi q-bits alla volta (ad esempio si è riusciti a fattorizzare il numero 15 = 3 × 5).
Apparentemente, si è ancora distanti, ma in realtà potrebbe non mancare poi molto...
Contenuti soggetti a licenza d'uso