Algoritm de fattorizzazion de Shor

Lumbard ucidental Quest articol chì l'è scrivuu in lombard, grafia milanesa.

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.

SpiegazionModifiché

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

 
 
 

EsempiModifiché

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'ordenModifiché

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.

ImplicazionModifiché

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.

RiferimentModifiché

Vos corelaaModifiché