La Crittografia e l’algoritmo di Shor.
Ti sei mai chiesto perché quando invii una e-mail, viene effettuata una transazione bancaria oppure, più banalmete, quando si naviga su internet i nostri dati sono al sicuro?
Tutto ciò è possibile grazie alla crittografia. Oggi la più usata è la crittografia a chiave pubblica ("public-key"), basata sull'algoritmo RSA. Il sistema si basa sull'esistenza di due chiavi distinte, che vengono usate per cifrare e decifrare. Una di queste è pubblica, la public-key appunto, che serve per cifrare i dati, mentre la seconda è detta privata ed è segreta, solo la banca o il provider di posta elettronica la possiedono, ed è grazie ad essa che possono decifrare i dati, impedendo cosi a chiunque altro di potervi accedere.
Titolo: Modello di Crittografia Public-Key Autore: B140970113 Fonte: Creative Commons
Ma cosa sono queste chiavi? La public-key è, sostanzialmente, un numero molto grande, che chiameremo \(N \), il quale ha una proprietà specifica, è fattore di due numeri primi \(a \) e \(b \), anche loro molto grandi, se fossimo a conoscenza dei due fattori di \(N \) ( \(N = a*b \) ) saremmo in grado di creare la chiave privata e quindi decriptare il messaggio. Trovare questi due fattori di \(N \) è un operazione molto lunga, perfino gli algoritmi più ottimizzati, a noi conosciuti, che lavorano sui computer classici richiedono migliaia di anni per essere portati a termine, risultando dunque impraticabili.
Titolo: Esempio di Chiave Pubblica Autore: Χρήστης:Chggr Fonte: Creative Commons
Ma grazie all'algoritmo di Shor, inventato nel 1994 da Peter Shor, che opera su un computer quantistico, il problema della fattorizzazione potrebbe avere una soluzione in tempi ragionevoli. Prima di tutto partiamo con il ragionamento che sta alla base dell'algoritmo, scegliamo casualmente un numero \(A \) che non condivide fattori con \(N \), moltiplicato \(p \)-volte per se stesso è uguale ad un multiplo di \(N \) più uno (Teorema cinese del resto). \[ A^p = mN+1 \]
Riordinando l'equazione otteniamo: \( A^p-1 = mN \Rightarrow (A^{p/2}+1)(A^{p/2}-1) = mN \). Notiamo che \(N \) non divede i due termini, ma grazie ad un algoritmo conosciuto da duemila anni (Algoritmo di Euclide), possiamo trovare i fattori comuni, e risolvere il problema della fattorizzazione. Però con questa procedura sorgono due problemi:
Il nostro \(p \) postrebbe essere dispari, creando numeri irrazionali come \(7^{ \frac{3}{2} } (=18.520259...)\), inutilizzabili;
Uno dei due fattori potrebbe essere un multiplo di \(N \), rendendo inutile l'algoritmo di Eulero.
L'unica soluzione è tentare con un nuovo numero \(A \) casuale, ripetendo il procedimento.
Ma come troviamo \(p \)? Qui ci viene in aiuto il computer quantistico, grazie al quale possiamo calcolare simultaneamente tutte le possibili combinazioni di potenze \(x \) elevate al nostro \(A \), ottenendo cosi uno un insieme di stati sovrapposti ("superposition"), al quale applicando l'operazione modulo otteremo il resto della divisione per \(N \) (in forma compatta: \(A^x mod N = resto \) ), ricordo che noi stiamo cercando il resto \(1 \).
\[ |1\rangle + |2\rangle + |3\rangle + ... \Longrightarrow |A^1\rangle + |A^2\rangle + |A^3\rangle + ... \Longrightarrow \] \[ \Longrightarrow |A^1modN\rangle + |A^2modN\rangle + |A^3modN\rangle + ... \]
[NOTA: questo è quello che in modo molto semplificato avviene ai qubit sovrapposti]
Se misurassimo gli stati, secondo le leggi della meccanica quantistica, avremmo un eguale possibilità di ottenere un solo risultato tra tutti gli elementi, ciò sarebbe inutile. Mentre basandoci su un altra osservazine, il resto di \(1 \) accorre in manira periodica, questo periodo è proprio il nostro \(p \)! Grazie alla trasformata quantica di Fourier possiamo estrapolare il periodo \(p \) dalgli stati e finalmente riusciamo a risolvere il problema!
Nel 2001 la IBM ha dimostrato la validità dell'algoritmo, fattorizzando \(15 \) in \(5 \) e \(3 \). Link all'articolo pubblicato su Nature.
baratheonpilled
stormborns
janainaart
annaxmalina
yousharknotpass
2087
discoholicmusic
dededos