WikiDer > Miller-Rabin-Primzahltest

Das Miller-Rabin-Primzahltest oder Rabin-Miller-Primzahltest ist ein Primzahltest: ein Algorithmus das bestimmt, ob eine gegebene Zahl Ahle ist oder nicht. Es ist ähnlich wie die Fermat-Prime-Test und der Solovay-Straßen-Primzahltest, die wie der Miller-Rabin-Primzahltest häufig in der Kryptographie. Die Originalversion dieses Tests wurde erstellt von Gary L. Miller und ist deterministisch. Der deterministische Teil dieses Tests hängt jedoch von den noch nicht bewiesenen Riemann-Hypothese. Michael O. Rabin änderte den Test zu a Wahrscheinlichkeitsrechnung test, der von nichts abhängt und immer funktioniert.

Theorie

Das Prinzip des Miller-Rabin-Primzahltests ist das gleiche wie das des Fermat-Tests und der Solovay-Straßen-Primzahltest: für eine oder mehrere Eigenschaften von Primzahlen wird geprüft, ob die zu testende Zahl diese Eigenschaft oder Eigenschaften besitzt. Wenn nicht, ist die Zahl keine Primzahl. Wenn ja, kann nur geschlossen werden, dass die Zahl möglicherweise (wahrscheinlich) eine Primzahl ist.

Lemma

Das nächste Lemma betrifft Quadrat-Wurzeln der Einheit in dem endlicher Körperz/pz vor dem p eine ungerade Primzahl. Natürlich ergeben 1 und −1 immer 1 wenn sie modularp einbiegen in kariert; Dies sind die trivial QuadratWurzeln von 1 (mod p).

Das Lemma lautet: Es gibt keine nicht trivial Quadratwurzeln von 1 (mod p).

Beweise

Paar

${displaystyle x^{2}Äquiv. 1{pmod {p}}}$,

als

${displaystyle (x-1)(x 1)=x^{2}-1equiv 0{pmod {p}}.}$

Das bedeutet, dass ${displaystyle p}$ ist ein Teiler von ${Anzeigestil x-1}$ oder von ${Anzeigestil x 1}$. Daraus folgt

${displaystyle x-1äquiv 0{pmod {p}},}$ So ${displaystyle xequiv 1{pmod {p}}}$

oder

${Anzeigestil x 1 Äquiv. 0 {pmod {p}},}$ So ${displaystyle xequiv -1{pmod {p}}.}$

Das Prinzip des Tests

Sie ${Anzeigestil n>2}$ eine Primzahl. Dann ist ${Anzeigestil n-1}$ Sag nur ${Anzeigestil n-1=2^{s}d}$, mit ${Anzeigestil s}$ und ${displaystyle d}$ positive ganze Zahlen und ${displaystyle d}$ seltsam. Für jedes ${displaystyle ain (mathbb {Z} /nmathbb {Z} )^{*}}$ entweder das

${displaystyle a^{d}äquivalent 1{pmod {n}}}$

entweder das

${displaystyle a^{2^{r}cdot d}equiv -1{pmod {n}}}$ für eine gewisse ${displaystyle 0leq rleq s-1}$.

weil sie ${displaystyle ain {2,3,ldots,n-2}}$, dann nach Der kleine Satz von Fermat wenn ${displaystyle n}$ eine Primzahl ist:

${displaystyle a^{n}äquivalent a{pmod {n}}.}$

Daraus folgt auch:

${displaystyle a^{n-1}=a^{2^{s}d}äquivalent 1{pmod {n}}.}$

Durch wiederholtes Auswurzeln ${Displaystil a^{n-1}}$ nach dem vorherigen Lemma ist das Ergebnis 1 oder -1. Wenn das Ergebnis -1 ist, dann gilt anscheinend die zweite Äquivalenz und der Beweis ist erbracht. Ist das Ergebnis alles ${Anzeigestil s}$ mal immer 1, dann bleibt die erste Äquivalenz.

Prüfung

Der Miller-Rabin-Primzahltest basiert auf dem Kontraposition der oben genannten: Wenn es a . gibt ${displaystyle ain {2,3,ldots,n-2}}$ gefunden wird, wofür

${displaystyle a^{d}nicht gleich 1{pmod {n}}}$

und

${displaystyle a^{2^{r}cdot d}ot equiv -1{pmod {n}}}$ für alle ${displaystyle 0leq rleq s-1,}$

dann ist ${Anzeigestil a}$ ein Zeuge aus der Tatsache, dass ${displaystyle n}$ zusammengesetzt ist. anders ist ${displaystyle n}$ sehr wahrscheinlich prim mit Sockel ${Anzeigestil a}$. Ist ${displaystyle n}$ jedoch zusammengesetzt, heißt dann ${Anzeigestil a}$ ein Lügner vor dem ${displaystyle n}$.

Für alle ungeraden Verbindungen ${displaystyle n}$ es gibt viele Zeugen, aber es gibt keinen bekannten einfachen Weg, einen solchen Zeugen zu finden. Die Lösung besteht darin, den Test probabilistisch zu machen: Wählen Sie zufällig einen aus ${displaystyle ain (mathbb {Z} /nmathbb {Z} )^{*}}$, und sehen Sie, ob es ein Zeuge für die Zusammensetzung von ist ${displaystyle n}$. wenn ${displaystyle n}$ zusammengesetzt ist, werden die meisten Auswahlmöglichkeiten Zeuge des Zusammensetzens und der Test wird es höchstwahrscheinlich entdecken. Es bleibt jedoch eine kleine Chance, dass die Auserwählten ${displaystyle n}$ ein starker Lügner ist für ${displaystyle n}$. Die Wahrscheinlichkeit solcher Fehler kann durch Wiederholung des Tests für mehrere unabhängig ausgewählte ${Anzeigestil a}$.

Beispiel

Angenommen, die Zahl ${Anzeigestil n=221}$ auf Vorrang geprüft. schreiben ${Displaystil n-1=220=2^{2}imes 55}$, So ${Anzeigestil s=2}$ und ${Anzeigestil d=55}$. Wählen Sie eine ${displaystyle a$, beispielsweise ${displaystyle a=174}$ und schau dir die Äquivalenzen an:

${displaystyle a^{d}=174^{55}Äquiv. 47ot Äquiv. 1{pmod {221}}}$

${displaystyle a^{s^{0}cdot d}=174^{55}Äquiv. 47ot Äquiv. -1{pmod {221}}}$

${displaystyle a^{s^{1}cdot d}=174^{110}Äquiv 220Äquiv -1{pmod {221}}}$

So ist für einen ${displaystyle r}$ für die ${displaystyle 0leq r$ die gewünschten Äquivalenzen werden nicht erfüllt, so dass 174 nicht bezeugt, dass 221 zusammengesetzt ist. Also ist entweder 221 eine Primzahl oder 174 ist ein Lügner für 221. Wähle einen anderen another ${Anzeigestil a}$, beispielsweise ${displaystyle a=137}$. Schauen Sie sich noch einmal die Äquivalenzen an:

${displaystyle a^{d}=137^{55}Äquiv. 188ot Äquiv. 1{pmod {221}}}$

${displaystyle a^{s^{0}cdot d}=137^{55}Äquiv. 188ot Äquiv. -1{pmod {221}}}$

${displaystyle a^{s^{1}cdot d}=137^{110}Äquiv. 205ot Äquiv. -1{pmod {221}}}$

137 ist also ein Zeugnis dafür, dass 221 zusammengesetzt ist und 174 tatsächlich ein Lügner war. Beachten Sie, dass wir nichts über die Faktoren von 221 (nämlich 13 und 17).

Algorithmus

Der Algorithmus kann Pseudocode wie folgt beschrieben werden:

Eingang: nein > 2, eine ungerade ganze Zahl, die auf Primalität getestet wurde; k, eine ganze Zahl, die die Genauigkeit des Tests bestimmtExport: zusammengesetzt wenn nein ist zusammengesetzt, anders wahrscheinlich prim   schreiben nein-1 als 2so·d mit d ungerade mit Potenzen von 2 aus nein−1 Möglichkeit, LOOP zu teilen: wiederholen k mal: wähle 2 ≤ein ≤ nein−2 zufällig X ← eind mod neinX = 1 oder X = nein−1 dann mach die nächste LOOP r = 1,...,so−1         X ← X2 mod neinX = 1 dann Ausgabe zusammengesetztX = nein-1 dann führe die folgende LOOP-Ausgabe aus zusammengesetztAusgabe wahrscheinlich prim

Richtigkeit

Wie gesagt: für die mehr Zahlen ein Wir führen den Test durch, desto genauer ist der Test. Es wurde bewiesen^[1] dass für jede ungerade zusammengesetzte Zahl nein, mindestens 3/4 der Basen ein bezeugen, dass nein zusammengesetzt ist. Also wenn nein zusammengesetzt ist, dann erklärt der Miller-Rabin-Primzahltest nein als wahrscheinliche Primzahl mit Wahrscheinlichkeit höchstens 4^−k. In dieser Hinsicht erhebt sich dieser Test über den Primzahltest von Solovay-Strassen, da er eine zusammengesetzte Zahl als wahrscheinliche Primzahl mit einer Wahrscheinlichkeit von höchstens 2 . deklariert^−k.

Verweise

Externe Links

• (und) Arnold, F., Rabin-Miller-Primalitätstest: Zusammengesetzte Zahlen, die ihn bestehen, Mathematik der Berechnungen Vol. 2, No. 64 (1995), Nr. 209, S. 355-361.
• (und) Hurd, J., Überprüfung des probabilistischen Primzahltests nach Miller-Rabin, The Journal of Logic and Algebraic Programming Vol. 2, No. 56 (2003), p. 3-21.