Shors Algorithmus schränkt ein, wenn

8

Damit eine ganze Zahl faktorisiert wird, wobei (gleichmäßig) zufällig zwischen und , wobei der Größenordnung von ( das kleinste mit ). ::Na1NramodNrar1modN

Warum müssen wir in Shors Algorithmus das Szenario verwerfen, in dem ar/2=1modN ? Warum sollten wir das Szenario nicht verwerfen, wenn ar/2=1modN ?

Technischer Löser
quelle
Dies hat nicht unbedingt mit Quantencomputing zu tun. Wir sprechen hier über den klassischen Algorithmus. Es ist nur so, dass Shors Algorithmus uns eine gute Möglichkeit bietet, die Reihenfolge zu finden, r , aber Sie können dies auch klassisch tun.
DaftWullie
1
@DaftWullie Obwohl das stimmt, können Sie dies nur wissen, wenn Sie den Shor-Algorithmus kennen (dh QC-Kenntnisse). Die Frage lautete: "Warum können wir Shor nicht für diese Eingaben verwenden?" geht es um QC. Die Antwort enthält nicht viel QC, aber um zu wissen, welche Antwort Sie geben müssen, müssen Sie dennoch über Shors Algorithmus Bescheid wissen.
Diskrete Eidechse

Antworten:

2

Die Anforderung, dass ist, entspricht der Anforderung, dass .ar1modNar10modN

Wir wollen eine Zahl, , so dass der größte gemeinsame Nenner von und ein geeigneter Faktor von (dh ein Faktor ).bbNN1,N

Wir haben auch, dass .ar1=(ar/21)(ar/2+1)

Wir nehmen also . Wir wissen, dass die kleinste Zahl ist, so dass , was zeigt, dass und damit (wie sonst würde teilen ).b=ar/21rar=1modNar/21modNgcd(ar/21,N)NNb

Nach Bézouts Identität existiert oder . Wenn teilt , ergibt dies, dass oder teilt .gcd(ar/21,N)=1,x1,x2Z s.t. (ar/21)x1+Nx2=1(ar1)x1+N(ar/2+1)x2=ar/2+1Nar1Nar/2+1ar/2=1modN

Dies ergibt, dass die Anforderung (neben der Bedingung für ) ausreicht, um zu bestimmen, dass der größte gemeinsame Nenner von und ein Eigenwert ist Faktor .ar/21modNrar/21NN

Mithrandir24601
quelle
2

Es gibt kein Szenario für da Sie bereits angenommen haben, dass der kleinste Wert ist, so dass und ist kleiner als .ar/21 mod Nrar1 mod Nr/2r

Wenn Sie wissen, warum Sie diskontieren müssen , ist der Punkt, dass Sie etwas gefunden haben, das für eine ganze Zahl erfüllt . Dies faktorisiert als wenn ist. Entweder einer der Begriffe teilbar ist durch , oder jede enthält verschiedene Faktoren von . Wir möchten, dass sie verschiedene Faktoren enthalten, damit wir Computer , um einen Faktor zu finden. So wollen wir ausdrücklich , dass . Ein Fall wurde wie oben angegeben beseitigt, indem verlangt wurdear/21 mod N(ar1)=kNk(ar/21)(ar/2+1)=kNr(ar/2±1)NNgcd(ar/2±1,N)ar/2±10 mod Nrso klein wie möglich sein. Den anderen müssen wir explizit rabattieren.

DaftWullie
quelle
2

Wenn , dann ist eine triviale Quadratwurzel von anstelle einer interessanten Quadratwurzel. Wir wussten bereits, dass eine Quadratwurzel von . Wir brauchen eine Quadratwurzel, die wir noch nicht kannten.ar/21ar/2111

Angenommen, ich gebe Ihnen eine Zahl so dass . Sie können diese Gleichung wie folgt umschreiben:xx2=1(modN)

x2=1+kNx21=kN(x+1)(x1)=kN

Der Schlüssel ist daran zu erkennen ist , dass diese Gleichung trivial ist , wenn istx±1modN . Wenn , dann ist die linke Seite weil der Faktor . Das gleiche passiert, wenn , aber mit dem anderen Faktor.x10modN(x+1)0x+1

Damit sowohl als auch interessant sind (dh nicht Null mod ), muss eine zusätzliche Quadratwurzel von . Eine Quadratwurzel neben den offensichtlichen Antworten und . Wenn dies geschieht, ist es unmöglich, dass die Primfaktoren von alle in oder alle in , und so gibt Ihnen garantiert einen Faktor von anstelle eines Vielfachen von .(x+1)(x1)Nx1+11N(x+1)(x1)gcd(x+1,N)NN

Wenn zum Beispiel dann ist eine zusätzliche Quadratwurzel von 1. Und tatsächlich sind sowohl als auch sind Faktoren von . Wenn wir die langweilige Quadratwurzel , wäre weder noch sind Faktoren von .N=221x=103gcd(x+1,N)=gcd(104,221)=13gcd(x1,N)=gcd(102,221)=17221x=1220gcd(x+1,N)=gcd(221,221)=221gcd(x1,N)=gcd(219,221)=1221

Craig Gidney
quelle