Algoritm de fattorizzazion de Shor

Modell:MILCLASS L'algoritm de fattorizzazion de Shor a l'è on algoritm che 'l se pò doperà per fattorizzà i numer compost in numer primm. In su 'n computer quantich a l'è in BQP, ossia la se pò resoeulv cont on margin de error arbitrariament piscininn in d'on temp polinomial in la longhezza de l'input.

A l'è teorizzaa in del 1994 dal Peter Shor e l'è staa demostraa in del 2001 cont on computer quantich a 7 qubit de la IBM che l'ha fattorizzaa 15 in 3x5. In del 2012, inveci, a l'è staa fattorizzaa el numer pussee volt: 56'153.

Spiegazion

Che 'l sia $n$ el numer de fattorizzà. El problema el se pò ridù a log(n) problema de fattorizzazion binaria minga per forza primm.

A l'è scernuu on numer $a<n$ inscì che $a$ el sia coprimm con $n$: el massim comun divisor in tra i du el var donca 1.

Se da ona succession de numer positiv $k$:

$f(k)=a^k(\mathrm{mod}n)$

Inscì che vun di termen de la succession l'è vun e i alter se ripeten ciclicament, ossia

$f(k+t)=f(t)$ per i intregh $k>r$ e per on period daa $t$.

$r$ l'è el pussee piscininn per che $f(r)=a^r(\mathrm{mod}n)=1$, e se dis orden moltiplicativ de $a$ modul $n$. L'è anca el period de succession.

Se $r$ l'è pari, almen vun di fattor de $n$ si l'è in tra i du numer

• $MCD((a^{r/2}+1),n)$
• $MCD((a^{r/2}-1),n)$

De facc

$a^r=1(\mathrm{mod}n)$

$(a^{r/2}{)}^2-1=0(\mathrm{mod}n)$

$(a^{r/2}+1)*(a^{r/2}-1)=0(\mathrm{mod}n)$

Esempi

Per esempi con n=143 e se scernissom a=21, l'orden l'è 4 ($f(4)=21^4(\mathrm{mod}143)=1$).
var $(21^{4/2}-1)(21^{4/2}+1)=0(\mathrm{mod}143)=>440\cdot 442=0(\mathrm{mod}143)$.
I MCD in tra i termen e $n$ hinn i candidaa fattor primm.

$MCD(440,143)=11$

$MCD(442,143)=13$

che de facc a hinn i fattor primm de $n$, 11 e 13.

Calcolà de l'orden

El calcolà de l'orden a l'è on problema che 'l se cognoss no ona soluzion deterministica efficenta. La soluzion del Peter Shor a l'è de doperà i proprietà speciai de l'informatega quantistega per permett de trovàll in d'on temp polinomial.

El facc che 'l sia quantistich el rend on algoritm probabilistich, e per vess segur de la soluzion a l'è donca necessari eseguìll pussee de 'na voeulta.

Implicazion

Se 'l fuss possibil eseguì l'algoritm de Shor cont di qubit che hinn assee el saria possibil scassà i formi de crittografia asimmetrega fondaa in su la fattorizzazion o in sul logaritm discrett in d'on temp tollerabil.

Riferiment

• Algoritmo di Shor

Vos corelaa

• Algoritm quantistich