Algoritmo di fattorizzazione di Shor

L'algoritmo di fattorizzazione di Shor è un algoritmo ideato da Peter Williston Shor nel 1994 per risolvere il problema della fattorizzazione dei numeri interi in numeri primi.

Su un computer quantistico questo algoritmo ha una complessità computazionale BQP (Bounded error Quantum Polynomial time): i fattori primi vengono trovati con un margine d'errore arbitrariamente piccolo in un "tempo polinomiale" legato alla lunghezza del numero intero da fattorizzare.

Procedura

Introduzione

L'algoritmo di Shor consiste di due passi:

una riduzione, che può essere eseguita su un computer classico, del problema di fattorizzazione a un problema di calcolo dell'ordine moltiplicativo;
la risoluzione, tramite un algoritmo quantistico, del problema del calcolo dell'ordine moltiplicativo.

Riduzione del problema

Sia $N$ il numero da fattorizzare.

Passo 1

Viene scelto un numero intero casuale $a < N$ .

Passo 2

Mediante l'algoritmo esteso di Euclide si calcola il massimo comun divisore tra i due, cioè $M C D (a, N)$ . Se $M C D (a, N) > 1$ , il risultato è uno dei due fattori di $N$ e il problema è risolto, altrimenti $M C D (a, N) = 1$ implica che $a$ è coprimo con $N$ e quindi esiste un $x$ inverso moltiplicativo del modulo $N$ tale che $a \cdot x \equiv 1 mod N$ (si veda ancora l'algoritmo esteso di Euclide). Essendoci l'inverso ed essendo i valori di $a$ limitati da $N$ , esso appartiene al gruppo moltiplicativo finito degli interi modulo $N$ , che è periodico, ossia esiste un intero $r$ (ordine moltiplicativo) tale che

a^{r} \equiv 1 mod N,

dove $r$ è il più piccolo intero positivo che soddisfa la congruenza. Infatti per valori dell'esponente di $a$ compresi tra 1 e $r - 1$ si ottengono elementi del gruppo moltiplicativo. Per valori tra $r$ e $2 r - 1$ si riottengono gli stessi elementi e così via per gli intervalli successivi ( $a^{r} \equiv a^{2 r} \equiv a^{3 r} ... \equiv 1 mod N$ ).

Passo 3

Calcolo dell'ordine $r$ con l'algoritmo quantistico.

Passo 4

Se $r$ è pari, almeno uno, se non entrambi i seguenti numeri sono fattori di $N$ :

$M C D (a^{r / 2} + 1, N),$
$M C D (a^{r / 2} - 1, N),$

infatti

a^{r} \equiv 1 (\mod N),

(a^{r / 2})^{2} - 1 \equiv 0 (\mod N),

(a^{r / 2} + 1) (a^{r / 2} - 1) \equiv 0 (\mod N) .

Se $r$ è dispari, non potendo essere diviso per due, si ritorna al passo 1 per generare un nuovo $r$ .

In questo modo si trovano due fattori di $N$ . Nel caso tali fattori non siano primi, vanno fattorizzati a loro volta. Si può arrivare al massimo a log(N) fattorizzazioni.

Esempio numerico

Dato $N = 143$ e scegliendo $a = 21,$ l'ordine moltiplicativo è $4$ , infatti $2 1^{4} \equiv 1 (\mod 143)$ .

Essendo $r$ pari, si prosegue con il passo 4, ottenendo

(2 1^{4 / 2} - 1) (2 1^{4 / 2} + 1) \equiv 0 (\mod 143),

da cui segue che $440 \cdot 442 \equiv 0 (\mod 143)$ .

I $M C D$ tra i due termini e $n$ sono i candidati fattori primi:

M C D (440, 143) = 11,

M C D (442, 143) = 13,

che sono effettivamente i fattori di $N$ , 11 e 13.

Calcolo dell'ordine

Individuare l'ordine è un problema di cui non si conosce una soluzione deterministica efficiente con un computer classico. L'introduzione di Peter Shor è quella di un algoritmo quantistico in grado di fornire l'ordine $r$ in un "tempo polinomiale" legato alla lunghezza di $n$ (con ciò si intende che se la lunghezza del numero $n$ è $m$ , allora l'algoritmo richiede un tempo polinomiale del tipo $O (m^{c})$ con $c > 0$ ).^[1] L'algoritmo utilizza la codifica e l'estrazione di informazioni (tramite la trasformata di Fourier quantistica) dalle fasi relative tra gli stati quantistici (qubit), proprietà che non ha un equivalente classico.

Esistono diverse versioni dell'algoritmo. Quella presentata da Shor nel 1994 è la seguente:^[2]

si considerino due registri, di $q$ e $m$ qubit. Il primo sia inizializzato alla rappresentazione binaria di $| 0 ⟩$ , ossia $| 0 ⟩^{\otimes q}$ . Il secondo a $| 1 ⟩$ , rappresentato su $m$ cifre come $| 0 ⟩^{\otimes m - 1} | 1 ⟩$ ;
sul primo registro si opera una porta di Hadamard a $q$ qubit. Il primo registro si trova così in uno stato $(| 0 ⟩ + | 1 ⟩)^{\otimes q}$ (si omettono le normalizzazioni). Si può osservare che questo stato è la sovrapposizione uniforme di tutti gli stati che codificano per numeri $x < 2^{q}$ ;
il primo registro controlla l'azione di $U_{a}^{x}$ sul secondo. L'operatore si definisce come $U_{a} | y ⟩ = | y a (\mod n) ⟩$ . L'operatore $U_{a}$ è una radice $r$ -esima dell'unità, dove $r$ è l'ordine moltiplicativo di $a$ modulo $n$ , ha quindi autovalori del tipo $e^{2 π i \frac{k}{r}}$ per $0 \leq k < r$ . Si può mostrare che la sovrapposizione omogenea degli autostati è esattamente lo stato $| 1 ⟩$ . Far controllare l'azione di $U_{a}^{x}$ allo stato del primo registro, in sovrapposizione di tutti gli $x < 2^{q}$ fa in modo che le fasi $e^{2 π i \frac{k}{r}}$ compaiano nello stato finale;
la trasformata di Fourier quantistica estrae queste fasi e le rende misurabili in base computazionale sul primo registro.

Diverse ripetizioni dell'algoritmo forniscono varie stime di $\frac{k}{r}$ , da cui si può riconoscere $r$ . Il $k$ misurato ad ogni esecuzione è casuale, tra tutti quelli minori di $r$ : da solo può risultare fuorviante (ad esempio se divide $r$ ).

Efficienza

L'algoritmo presentato ha complessità di ordine $\log^{2} N \cdot \log \log N \cdot \log \log \log N$ . La restante parte della fattorizzazione, espressa sopra, è comune agli algoritmi classici ed è già efficiente: l'accelerazione che l'algoritmo di Shor dà al problema del calcolo dell'ordine, quindi, rende efficiente l'intero algoritmo di fattorizzazione.

L'algoritmo, tuttavia, non è deterministico, ed ha una probabilità di successo minore di 1: si può comunque ripeterne l'iterazione per abbassare la soglia d'errore.

Implementazione

Non esiste una macchina quantistica scalabile che implementi la versione descritta dell'algoritmo di Shor. Versioni compilate, ossia ridotte per casi specifici, sono invece già state eseguite: ad esempio su sistemi ottici lineari, dove i qubit sono codificati nella polarizzazione dei fotoni.

Note

↑ John E. Hopcroft, Rajeev Motwani e Jeffrey D. Ullman, p. 392.
↑ (EN) Peter W. Shor, Algorithms for quantum computation. Discrete logarithms and factoring, in 35th Annual Symposium on Foundations of Computer Science. Proceedings; November 20-22, 1994, Santa Fe, New Mexico, IEEE Computer Society Press, 1994, pp. 124–134, ISBN 9780818665820.

Bibliografia

John E. Hopcroft, Rajeev Motwani e Jeffrey D. Ullman, Problemi intrattabili, in Automi, linguaggi e calcolabilità, 3ª ed., Torino, Pearson Italia (collana "Informatica"), 2017, ISBN 9788891907806.
(EN) Phillip R. Kaye, Raymond Laflamme e Michele Mosca, Finding-Orders, in An Introduction to Quantum Computing, Oxford, Oxford University Press, 2007, pp. 130–141, ISBN 978-0-19-857049-3. URL consultato il 7 novembre 2025.
(EN) Peter W. Shor, Algorithms for quantum computation. Discrete logarithms and factoring, in 35th Annual Symposium on Foundations of Computer Science. Proceedings; November 20-22, 1994, Santa Fe, New Mexico, IEEE Computer Society Press, 1994, pp. 124–134, ISBN 9780818665820.

Voci correlate

Portale Fisica

Portale Informatica

[1] John E. Hopcroft, Rajeev Motwani e Jeffrey D. Ullman, p. 392.

[2] (EN) Peter W. Shor, Algorithms for quantum computation. Discrete logarithms and factoring, in 35th Annual Symposium on Foundations of Computer Science. Proceedings; November 20-22, 1994, Santa Fe, New Mexico, IEEE Computer Society Press, 1994, pp. 124–134, ISBN 9780818665820.

[1]

[2]