Algoritm de fattorizzazion de Shor

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  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  inscì che  el sia coprimm con : el massim comun divisor in tra i du el var donca 1.

Se da ona succession de numer positiv : 

Inscì che vun di termen de la succession l'è vun e i alter se ripeten ciclicament, ossia 
 per i intregh  e per on period daa .

 l'è el pussee piscininn per che , e se dis orden moltiplicativ de  modul . L'è anca el period de succession.

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


De facc

 Esempi 
Per esempi con n=143 e se scernissom a=21, l'orden l'è 4 ().
var .
I MCD in tra i termen e  hinn i candidaa fattor primm.

che de facc a hinn i fattor primm de , 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

Categoria:Matematega
Categoria:Informatega quantistega
Fattorizzazion