Fondamenti e principi di elaborazione quantistica, spiegati quasi facili: L’ALGORITMO DI SHOR o della fattorizzazione dei grandi numeri.

L’algoritmo di Shor è un algoritmo quantistico che permette di fattorizzare in modo efficiente numeri interi molto grandi. Questo algoritmo ha importanti applicazioni nella crittografia, in particolare nella rottura dei sistemi basati sulla difficoltà della fattorizzazione, come il RSA.

Il funzionamento dell’algoritmo di Shor si basa su due fasi principali: la prima fase consiste nel trovare il periodo di una funzione periodica modulo n, dove n è il numero da fattorizzare. Questa prima fase richiede l’uso di un computer quantistico e sfrutta il fenomeno dell’interferenza quantistica per ottenere una misura probabilistica del periodo. La seconda fase consiste nel usare il periodo trovato per calcolare i fattori di n tramite l’algoritmo di Euclide; questa fase può essere eseguita su un computer classico e richiede solo operazioni aritmetiche.

L’algoritmo di Shor ha una complessità temporale polinomiale nel numero di bit di n, mentre gli algoritmi classici conosciuti hanno una complessità esponenziale. Questo significa che l’algoritmo di Shor può fattorizzare numeri molto più grandi di quelli trattabili con i metodi classici. Per esempio, con un computer quantistico di 2048 qubit si potrebbe fattorizzare un numero di 1024 bit in circa 10 minuti, mentre con un computer classico ci vorrebbero circa 300 trilioni di anni.

L’algoritmo di Shor rappresenta quindi una sfida per la sicurezza dei sistemi crittografici attuali, che si basano sull’ipotesi che la fattorizzazione sia un problema intrattabile. Se si disponesse di un computer quantistico sufficientemente potente e affidabile, si potrebbe violare la confidenzialità e l’autenticità dei messaggi scambiati con il RSA e altri protocolli simili. Per questo motivo, si sta studiando la possibilità di sviluppare nuovi sistemi crittografici resistenti agli attacchi quantistici, detti post-quantum.