Algoritm de fattorizzazion de Shor

De Wikipedia
Jump to navigation Jump to search
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.

Spiegazion[Mudifega | mudìfica 'l sorgènt]

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[Mudifega | mudìfica 'l sorgènt]

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[Mudifega | mudìfica 'l sorgènt]

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[Mudifega | mudìfica 'l sorgènt]

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.

Vos correlaa[Mudifega | mudìfica 'l sorgènt]