Fattorizzazione in Numeri Primi: Algoritmi Classici e Algoritmo Quantistico di Shor

Per fattorizzazione si intende quel processo di scomposizione di un numero intero nei suoi numeri costituenti chiamati numeri primi. I numeri primi sono numeri divisibili solo per uno e per se stessi. Nel corso della storia hanno affascinato molte personalità dell'ambiente scientifico e non solo. La sequenza dei numeri primi è molto irregolare, non è possibile stabilire a priori il numero primo successivo, e per qualsiasi matematico che cerca sempre un ordine in Natura, è una questione alquanto intrigante.

Un determinato numero può essere primo oppure composto, ossia risulta essere il prodotto di due o più numeri primi. Determinare i numeri primi che compongono un numero composto è un'operazione non sempre facile. Solo negli ultimi decenni, con l'avvento di Internet, c'è stata una vera e propria riscoperta di questa tematica. Questo rinnovato interesse per i numeri primi e per la fattorizzazione è dovuto al fatto che la sicurezza informatica, sia nelle comunicazioni telematiche che nella protezione dei dati, è basata proprio sui numeri primi e sulla difficoltà che si ha nel processo di fattorizzazione dei numeri composti. Se tali numeri fossero facili da fattorizzare non esisterebbe nessun tipo di sicurezza basato su questi principi.

Procedure che hanno come scopo quello di ricercare i numeri primi di uno specifico numero composto si sono evolute drasticamente nel corso degli ultimi anni. Tali procedure o meglio definibili come algoritmi di fattorizzazione, utilizzando una terminologia molto informale, hanno una durata di esecuzione molto elevata e non sono considerati veloci. Questa caratteristica se la si osserva dalla prospettiva della sicurezza informatica è un elemento positivo. Anche se si considera l'algoritmo più evoluto in termini di velocità di esecuzione si hanno molte difficoltà nel portare a termine la fattorizzazione di interi molto grandi.

Gli algoritmi di fattorizzazione trattati in questa tesi sono solo un piccolo esempio di vari metodi che hanno come comune denominatore un grosso limite: hanno bisogno di molte risorse di calcolo e di tempo esecutivo. Fino ad ora non si è riusciti ad escogitare un algoritmo che riuscisse a fattorizzare qualsiasi grande numero composto in poco tempo. I computer di oggi hanno raggiunto una potenza di calcolo impressionante ma nonostante questa potenzialità la fattorizzazione rimane un problema che si riesce a risolvere soltanto con tempi molto lunghi.

Una soluzione al problema della fattorizzazione potrebbe essere quella di sfruttare un nuovo tipo di calcolo basato sulla fisica quantistica. La fisica o meccanica quantistica può essere utilizzata per avere una drastica accelerazione nella risoluzione di problemi come quello della fattorizzazione. La computazione quantistica si differenzia da quella “classica” per alcune caratteristiche che suonano come controintuitive. Ad esempio la possibilità di avere un bit (anche se si parlerà di bit quantistici) in due stati nello stesso istante, in altre parole si può avere lo stato 0 e lo stato 1 nello stesso momento. Un altro fenomeno molto particolare è l'esecuzione di due o più operazioni in maniera simultanea. Inoltre c'è una singolare caratteristica nei registri con bit quantistici: l'esistenza di una correlazione tra i vari bit. Tale computazione per il momento non ha un riscontro fisico concreto (hardware utilizzabile), è un modello di calcolo teorico e come tale è stato analizzato.

Un interessante sviluppo nella computazione quantistica è stata la creazione dell'algoritmo di fattorizzazione di Peter Shor. Tale algoritmo è l'unico metodo che riesce a determinare i fattori primi di un numero in tempi più rapidi di qualsiasi altro algoritmo classico (secondo stime teoriche). L'algoritmo di Shor è costituito da un insieme di passi classici, in termini computazionali, e da una parte quantistica. Quest'ultima parte è quella fondamentale ma necessita di un calcolatore quantistico per essere eseguita. Per ovviare a questo problema si è utilizzato un programma che riproducesse la computazione quantistica, quindi l'algoritmo di Shor, in un normale computer. Tale programma prende il nome di simulatore o emulatore.

La simulazione dell'algoritmo di Shor riguarda l'intera computazione quantistica, ossia che ogni passo del metodo di Shor è stato riprodotto in un sistema classico come se fosse eseguito su un sistema quantistico. Attraverso questo procedimento si è analizzato il tempo di esecuzione del passo quantistico dell'algoritmo. E' importante sottolineare che la riproduzione di un sistema quantistico all'interno di un ambiente classico non è soddisfacente, nel senso che i molteplici fenomeni quantistici non possono essere riproposti in un normale calcolatore. Tale processo ha come effetto un ampio rallentamento della parte quantistica nell'esecuzione dell'algoritmo di Shor ma si potrà constatare come il passo quantistico è quello che occupa il maggior tempo di esecuzione dell'intera elaborazione dell'algoritmo.