Untergrenzen für den Zeitraum der ganzzahligen Faktorisierung?

11

1975 hat Miller gezeigt, wie man die Faktorisierung der ganzen Zahl reduziert , um die Periode r einer Funktion f ( x ) = a x zu findenNr so, dass f ( x + r ) = f ( x ) mit einigen zufällig ausgewählten a < N . Es ist bekannt, dass Shors Algorithmus r auf einem Quantencomputer effizientfinden kann, während angenommen wird, dass es für einen klassischen Computer unlösbar ist, r zu finden.f(x)=axmodNf(x+r)=f(x)a<Nrr

Meine Frage ist jetzt: Gibt es bekannte Untergrenzen für für zufälliges N ? Gibt es irgendwelche Grenzen für r, wenn N = p q wie in RSA gewählt wird? Offensichtlich r muss Ω ( log ( N ) ) , da sonst könnte man einfach auszuwerten f ( x ) auf O ( log ( N ) ) aufeinanderfolgenden Punkten , um herauszufinden , rrNrN=pqrΩ(log(N))f(x)O(log(N))rklassisch. Würde es ausreichen , RSA zu brechen , wenn es einen klassischen Faktorisierungsalgorithmus war , die nur auf die Verteilung der unter gewissen davon ausgeht , , z r & egr ; & THgr; ( N / log ( N ) ) oder r & egr ; & THgr; ( rrΘ(N/log(N))?rΘ(N)

Eine Präsentation von Carl Pomerance auf „ The multiplikative Ordnung mod im Durchschnittn “ zitiert Beweise dafür , dass ist O ( N / log ( N ) ) im Durchschnitt über alle N , aber ich bin mir nicht sicher , ob ein klassischer Algorithmus, der Faktor kann N unter Die Hypothese von r O ( N / log ( N ) ) würde RSA endgültig brechen. Kann N kontrovers gewählt werden, um r O ( N ) zu haben?rO(N/log(N))NNrO(N/log(N))N oder r O ( rO(N))?rO(N)

(Hinweis: Es gibt eine verwandte Frage zum generischen Factoring im Vergleich zum RSA-Factoring.)

Martin Schwarz
quelle

Antworten:

17

Wenn , ist die Periode r immer ein Teiler von ϕ ( N ) = l c m ( p - 1 , q - 1 ) . Wenn Sie p - 1 = 2 p ' und q - 1 = 2 q ' für p ' , q ' prime wählen , dann haben wir r p ' , wenn Sie nicht unglaublich viel Glück haben.N=pqrϕ(N)=lcm(p1,q1)p1=2pq1=2qp,q . Ich glaube auch, dass wir Primzahlen p mit p = 2 p ' + 1 effizient finden können, indem wirKandidaten zufällig auswählen und testen (dies gilt, wenn die Ereignisse, dass p und p ' Primzahlen sind, ungefähr unabhängig sind; ich weiß nicht, ob dies derFall isthat sich bewährt). Wenn Sie Ihre Primzahlen sorgfältig auswählen, ist RSA auch mit der zusätzlichen Hypothese über einfaches Factoring vor Angriffen geschützt.rpqN/4pp=2p+1pp

Ich vermute, dass Zufallszahlen oder N = p q äußerst unwahrscheinlich sind, dass r O ( √) istNN=pq, aber ich habe keinen Beweis dafür. Die HypotheserO(rO(N)ist extrem stark, und ich wäre nicht überrascht, wenn für diesen Fall bereits ein effizienter Factoring-Algorithmus bekannt wäre.rO(N)

Peter Shor
quelle