Gibt es einen effizienten Algorithmus zum Testen der Primalität für Zahlen der Form

8

Ich habe CLRS gelesen und es wollte zeigen, dass wenn eine Primzahl der Form und ein quadratischer Rest ist, eine Quadratwurzel ist (man kann auch leicht zeigen, dass ist eine Quadratwurzel).pa a k + 1 a - k4k+3aak+1ak

Ich habe mich gefragt, ob unter Verwendung der vorherigen Tatsache und auch, dass wir wussten, dass wir eine Zahl der Form (nicht unbedingt Primzahl), dann gibt es vielleicht einen anderen Primalitätstest für (irgendein?) Verwendung der Quadratwurzelfunktion (dh ).N S Q R T N ( a ) = a k + 1N=4k+3NSQRTN(a)=ak+1

Der Algorithmus, den ich dachte, war folgender:

Wählen Sie einen quadratischen Rest (QR) (Sie können dies leicht tun, indem Sie prüfen, ob ein ^ {\ frac {p-1} {2}} \ equiv 1 \ pmod p gilt). Sobald wir einen QR haben, berechnen Sie a ^ {k + 1} = x_a und prüfen Sie, ob x_a ^ 2 gleich a ist . Wenn es wahr ist, schließen wir, dass a eine Primzahl ist. Andernfalls wählen wir einen anderen QR a '\ in \ mathbb {Z} ^ * _ N und wiederholen den Algorithmus. Man kann diesen Algorithmus k mal wiederholen . Wenn nach k- mal kein Erfolg vorliegt, schließen Sie, dass die Zahl zusammengesetzt ist.aZNap121(modp)x 2 a a a a 'Z * N k kak+1=xaxa2aaaZNkk

Ich habe hauptsächlich eine Vorstellung davon, warum es richtig ist, aber kein formaler Beweis. von der ersten Tatsache, dass eine Quadratwurzel ist, wenn eine Primzahl ist, muss dies bedeuten, dass . Wenn also ein QR ist, besteht diese Prüfung (die Hälfte der Zeit, in der wir einen QR wählen, ist die Wahrscheinlichkeit, dass wir einen Nicht-QR wählen, nur 1/2). p x 2 aaxa=ak+1paxa2a(modp)a

Wenn jedoch zusammengesetzt ist, haben wir anscheinend keine Garantie dafür, dass . Wenn es also nicht hält, sind wir sicher, dass es nicht prim ist. Aber wenn es dann gilt, wenn es seine Primzahl ist, haben wir Recht, aber wenn es zusammengesetzt ist, könnten wir falsch liegen? Ist es grundsätzlich möglich, die SQRT-Funktion zu verwenden, wenn , um zu entscheiden, ob eine Primzahl ist oder nicht?x 2 aaNN = 4 k + 3 N.xa2a(modN)N=4k+3N


Ich dachte auch an einen anderen Algorithmus, der seine eigene Frage verdient: Ist die Berechnung einer Quadratwurzel einer Zahl und mehr als zwei Wurzeln eine zuverlässige Methode, um die Primalität zu bestimmen?

Charlie Parker
quelle
@ Kyle Jones, gibt es eine Chance, dass Sie bereit sind, Ihre Antwort wiederherzustellen (wiederherzustellen)? Ich denke, es hat einen schönen Einblick - ich habe es auf den ersten Blick nicht ganz geschätzt, aber bei näherer Betrachtung denke ich, dass es ein schönes Beispiel ist.
DW
@ DW OK. Ich dachte nicht, dass es angesichts Ihrer umfassenderen Antwort viel Wert hat, aber ich werde es zurückbringen, wenn Sie denken, dass es sich lohnt.
Kyle Jones
Ich hatte eine neue Idee, nachdem ich Miller-Rabin überprüft hatte. Was denkst du über meinen neu vorgeschlagenen Algorithmus? @ KyleJones
Charlie Parker
@CharlieParker Wenn Sie eine neue Frage haben, sollten Sie diese in einem separaten Beitrag stellen. Wenn Sie diese Frage so bearbeiten, dass vorhandene Antworten ungültig werden, wird der Zweck der Speicherung von Fragen und Antworten zunichte gemacht.
Kyle Jones
@ KyleJones ist schwer zu entscheiden, weil es wirklich um das gleiche Thema geht. Was schlagen Sie vor? Ich kann eine neue Frage stellen, ich war mir nur nicht sicher, ob es angemessen war.
Charlie Parker

Antworten:

5

Lassen Sie mich mit einem Gegenbeispiel beginnen, bei dem Ihr Algorithmus die falsche Antwort gibt: dh wobei ist, Ihr Algorithmus jedoch zu dem Schluss kommt, dass es eine Primzahl ist. Angenommen, und . Dann ist , also besteht Ihren Scheck als QR. Außerdem ist und , sodass dies Ihren zweiten Test besteht. Ihr Algorithmus wird dies tun schlussfolgern, dass 91 prim ist. 91 ist jedoch keine Primzahl: . Daher hat Ihr Algorithmus in diesem Fall die falsche Schlussfolgerung gezogen. Dies zeigt, dass Ihr Algorithmus zumindest in einigen Fällen falsche Antworten ausgeben kann.N = 91 a = 9 a ( N - 1 ) / 2 = 9 451NN=91a=9a a ( N + 1 ) / 4 = 9 2381a(N1)/2=9451(mod91)a81 29a(N+1)/4=92381(mod91)91 = 7 × 138129(mod91)91=7×13


Tatsächlich gibt es ein ernsthafteres Problem mit Ihrem Algorithmus. Es gibt keine Nummer bei der Ihr Algorithmus jemals "Composite" ausgeben wird. Es denkt, dass alle Zahlen Primzahlen sind. Genauer gesagt, für jedes wird Ihr Algorithmus entweder für immer eine Schleife durchlaufen (wobei er versucht, eine Zahl zu finden, die den QR-Test vergeblich besteht) oder "prime" beenden und ausgeben. Ihr Algorithmus ist also so falsch wie möglich.N.NN

Sie können dies sehen, indem Sie eine Zahlentheorie anwenden. Sie haben einen Test, ob ein QR ist, und einen zweiten Test, der auf der Quadratwurzel-Einsicht basiert. Wenn den ersten Test besteht, besteht es den zweiten.aaa

Hier ist der Grund. Ihr QR-Test ist erfolgreich, wenn . Ihr zweiter Test erfolgreich ist, wenn . Letzteres ist gleichbedeutend mit . Aber . Wenn also , dann sehen wir (Multiplikation beider Seiten mit ) sofort, dass wir .( a ( N + 1 ) / 4 ) 2aa(N1)/21(modN)a ( N + 1 ) / 2a(a(N+1)/4)2a(modN)a ( N + 1 ) / 2a × a ( N - 1 ) / 2a(N+1)/2a(modN)a ( N - 1 ) / 21a(N+1)/2a×a(N1)/2(modN)a a ( N + 1 ) / 2aa(N1)/21(modN)aa(N+1)/2a(modN)

Jeder der Durchgänge Ihres Algorithmus läuft im Wesentlichen darauf hinaus, nach einem zu suchen , das den ersten Test besteht, und dann zu prüfen, ob es den zweiten Test besteht - aber basierend auf den vorherigen Erkenntnissen sehen wir, dass jedes , das den ersten Test besteht, dies tut garantiert auch den zweiten Test bestehen. Wenn der Algorithmus jemals einen Wert , der den QR-Test besteht, besteht der zweite Test automatisch und der Algorithmus gibt "prime" aus.a a akaaa

Die Lektion, die Sie lernen sollten: Jedes Mal, wenn Sie glauben, einen Algorithmus zu haben, der vielversprechend aussieht, lohnt es sich, ihn zu codieren und an einigen Testfällen auszuprobieren, um festzustellen, ob er gut zu funktionieren scheint. Das Ausprobieren einiger Testfälle ist kein Ersatz für einen Korrektheitsnachweis , kann jedoch hilfreich sein, um einen falschen Algorithmus schnell auszusortieren.


Abschließend zu Ihrer eigentlichen Frage: Können wir so etwas verwenden, um einen Primalitätstest zu erstellen? Nun, Sie können sich den Miller-Rabin-Primalitätstest als lose Grundlage für so etwas vorstellen. Sie basieren auf einer Charakterisierung, wie die Quadratwurzeln von aussehen sollten, wenn eine Primzahl ist. Wenn Sie auf eine Quadratwurzel von stoßen , die nicht oder , können Sie daraus schließen, dass keine Primzahl ist. Es ist jedoch nicht auf Zahlen der Form , also ist es in diesem Sinne definitiv anders.N 1 1 - 1 N N N = 4 k + 31N111NNN=4k+3

DW
quelle
Ich hatte eine neue Idee, nachdem ich Miller-Rabin überprüft hatte. Was denkst du über meinen neu vorgeschlagenen Algorithmus?
Charlie Parker
1
@CharlieParker Anstatt die Frage so zu bearbeiten, dass vorhandene Antworten ungültig werden, möchten wir normalerweise, dass Sie eine neue Frage stellen. Ich schlage vor, dass Sie das tun. (Hinweis: Überlegen Sie, wie Sie sqrt berechnen möchten ...)
DW
3

Die Kongruenz gilt für alle Primzahlen der richtigen Form, aber auch für einige zusammengesetzte Zahlen, wodurch die Kongruenz allein als Primalitätstest unbrauchbar wird.p

Beispiel: setze auf die Zahl , die offensichtlich zusammengesetzt ist und die Form mit . ist , also erzeugt mod den quadratischen Rest = . = = ; das Anwenden von mod darauf ergibt . Nun der Test: Unter Mod soll nur dann die Quadratwurzel von ( ) sein, wenn Primzahl ist, aber15 4 k + 3 k = 3 10000 100 2 10000 15 a 10 10 k + 1 10 4 10000 p 10 p 10 a 10 p 10 2 100 10 p p pp154k+3k=31000010021000015a1010k+110410000p10p 10a10p102 = was mod , also hat den Primailty-Test bestanden. Wir wissen jedoch, dass ist.10010ppp

Dies zeigt, dass der Algorithmus auch dann fehlerhaft sein kann, wenn Ihre Methode zur Auswahl von QRs perfekt ist. Zum Beispiel wäre hier ein vernünftiger Weg, um auszuwählen : Wählen Sie eine Zufallszahl , quadrieren Sie sie und nennen Sie das Ergebnis (dh ). Dann wissen Sie, dass garantiert ein QR ist und Sie es nicht mit dem von Ihnen aufgelisteten Test testen müssen. Wenn das war , wie Ihr Algorithmus nahm , dann das obige Beispiel zeigt , dass Ihr Algorithmus die falsche Antwort in einigen Fällen geben kann (zB , ).araa a p = 15 r = 5a=r2modNaap=15r=5

Kyle Jones
quelle
Ich frage mich, ob irgendwo in Ihren Berechnungen ein Fehler vorliegt oder ob ich den vorgeschlagenen Algorithmus falsch verstehe. besteht den QR-Test nicht: , nicht . Daher würde nach meinem Verständnis des vorgeschlagenen Algorithmus nicht als QR akzeptiert und der Algorithmus würde nicht versuchen, weitere Berechnungen damit durchzuführen. Ich gehe davon aus, dass der Algorithmus einen akzeptablen QR findet, indem zufällig auswählt und testet, ob ; das scheint das zu sein, was der Text vorschlägt. a ( N - 1 ) / 2 = 10 710a=101 a = 10 a a ( N - 1 ) / 21a(N1)/2=10710(mod15)1a=10aa(N1)/21(modN)
DW
@ DW OK. Ihre Antwort ist sowieso insgesamt besser.
Kyle Jones
1
Ahh, wenn ich etwas genauer hinschaue, sehe ich, was los ist: 10 ist zwar ein QR, aber der Check glaubt fälschlicherweise, dass es kein QR ist. Also, wenn die Art und Weise der Algorithmus so gearbeitet , um eine Zufallszahl holen , quadratisch es und ruft das Ergebnis (dh ), dann Ihre Antwort ein gültiges Gegenbeispiel wäre - und das ist nicht eine unvernünftige Interpretation des vorgeschlagenen Algorithmus. Coole, nette Antwort! r a a = r 2 mod N.a(N1)/2=1(modN)raa=r2modN
DW