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

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).$p$a a k + 1 a - $4k+3$$a$$a^{k+1}$$a^{-k}$

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 + $N = 4k+3$$N$$SQRT_N(a) = a^{k+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.$a \in \mathbb{Z}^*_N$$a^{\frac{p-1}{2}} \equiv 1 \pmod p$x 2 a a a a ' ∈ Z * N k $a^{k+1} = x_a$$x_a^2$$a$$a$$a' \in \mathbb{Z}^*_N$$k$$k$

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 a ≡ $x_a = a^{k+1}$$p$$x_a^2 \equiv a \pmod p$$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 a ≡ $N$N = 4 k + 3 $x_a^2 \equiv a \pmod N$$N = 4k+3$$N$

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?

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 45 ≤ $N$$N=91$$a=9$a a ( N + 1 ) / 4 = 9 23 ≡ $a^{(N-1)/2} = 9^{45} \equiv 1 \pmod{91}$$a$81 2 ≡ $a^{(N+1)/4} = 9^{23} \equiv 81 \pmod{91}$91 = 7 × $81^2 \equiv 9 \pmod{91}$$91=7 \times 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$$N$

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.$a$$a$

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 ) 2 ≡ $a^{(N-1)/2} \equiv 1 \pmod N$a ( N + 1 ) / 2 ≡ $(a^{(N+1)/4})^2 \equiv a \pmod N$a ( N + 1 ) / 2 ≤ a × a ( N - 1 ) /$a^{(N+1)/2} \equiv a \pmod N$a ( N - 1 ) / 2 ≡ $a^{(N+1)/2} \equiv a \times a^{(N-1)/2} \pmod N$a a ( N + 1 ) / 2 ≡ $a^{(N-1)/2} \equiv 1 \pmod N$$a$$a^{(N+1)/2} \equiv a \pmod N$

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 $k$$a$$a$$a$

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 + $1$$N$$1$$1$$-1$$N$$N$$N=4k+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 $p$$15$$4k + 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$ = was mod , also hat den Primailty-Test bestanden. Wir wissen jedoch, dass ist.$100$$10$$p$$p$$p$

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 , ).$a$$r$$a$a a p = 15 r = $a =r^2 \bmod N$$a$$a$$p=15$$r=5$