Miller -Rabin -Primalitätstest

Das Miller -Rabin -Primalitätstest oder Rabin -Miller -Primalitätstest ist ein probabilistisch Primalitätstest: ein Algorithmus was bestimmt, ob eine bestimmte Zahl ist wahrscheinlich Prime sein, ähnlich wie Fermat -Primalitätstest und die Solovay -Strassen -Primalitätstest.

Es ist von historischer Bedeutung bei der Suche nach a Polynomzeit Deterministischer Primalitätstest. Die probabilistische Variante bleibt in der Praxis weit verbreitet, als einer der einfachsten und schnellsten bekannten Tests.

Gary L. Miller entdeckte den Test 1976; Millers Version des Tests ist deterministisch, aber seine Korrektheit hängt von der Unbewiesen ab Erweiterte Riemann -Hypothese.^[1] Michael O. Rabin modifizierte es, um eine bedingungslose zu erhalten Probabilistischer Algorithmus 1980.^[2][a]

Mathematische Konzepte

Ähnlich wie bei den Fermat- und Solovay -STRASS -Tests prüft der Miller -Rabin -Primalitätstest, ob eine bestimmte Eigenschaft, von der bekannt ist, dass sie für Prime -Werte gilt, für die untersuchende Zahl gilt.

Starke wahrscheinliche Primzahlen

Die Eigenschaft ist die folgende. Für eine bestimmte ungerade Ganzzahl n > 2, Lass uns schreiben n wie 2^s⋅d + 1 wo s und d sind positive Ganzzahlen und d ist ungerade. Betrachten wir eine Ganzzahla, genannt Base, so dass 0 << a < n. Dann, n soll ein sein stark Wahrscheinliche Primzahl zur Basis a Wenn einer davon Kongruenzbeziehungen hält:

• ${\ displayStyle a^{d} \ äquiv 1 {\ pmod {n}}}$;
• ${\ displaystyle a^{2^{r} \ cdot d} \ äquiv -1 {\ pmod {n}}}$ für einige 0 ≤ r < s.

Die Idee unter diesem Test ist das, wann n ist eine seltsame Primzahl, es besteht den Test aufgrund von zwei Fakten:

• durch Fermats kleiner Theorem, ${\ displayStyle a^{n-1} \ äquiv 1 {\ pmod {n}}}$ (Diese Eigenschaft allein definiert den schwächeren Begriff von Wahrscheinliche Primzahl für die Basis a, auf denen der Fermat -Test basiert);
• das einzige Quadratwurzeln von 1 Modulo n sind 1 und -1.

Daher von Schaffung, wenn n ist keine starke wahrscheinliche Primzahl für die Basis a, dann n ist definitiv zusammengesetzt, und a wird als a genannt Zeuge für die Kompositheit von n (manchmal irreführend genannt a starker Zeuge).

Diese Eigenschaft ist jedoch keine genaue Charakterisierung von Primzahlen. Wenn n ist zusammengesetzt, es kann dennoch eine starke wahrscheinliche Primzahl für die Basis sein aIn diesem Fall wird es a genannt Starke Pseudoprime, und a ist ein starker Lügner.

Auswahl der Basen

Zum Glück ist keine zusammengesetzte Zahl gleichzeitig ein starkes Pseudoprim für alle Basen. Es ist jedoch keine einfache Möglichkeit, einen Zeugen zu finden. Eine naive Lösung besteht darin, alle möglichen Basen auszuprobieren, was einen ineffizienten deterministischen Algorithmus ergibt. Der Miller -Test ist eine effizientere Variante davon (siehe Sektion Miller -Test unter).

Eine andere Lösung besteht darin, zufällig eine Basis zu wählen. Dies liefert schnell Probabilistischer Test. Wann n ist zusammengesetzt, die meisten Basen sind Zeugen, sodass der Test erkannt wird n als zusammengesetzt mit einer einigermaßen hohen Wahrscheinlichkeit (siehe Sektion Genauigkeit unter). Wir können die Wahrscheinlichkeit von a schnell reduzieren Falsch positiv zu einem willkürlich geringen Preis durch Kombination des Ergebnisses von so vielen unabhängig ausgewählten Grundlagen nach Bedarf, um diesen Satz zu erreichen. Dies ist der Miller -Rabin -Test. Die Anzahl der Basen, die sie ausprobieren können, hängt nicht ab davon n. Es scheint eine sinkende Renditen zu geben, wenn man viele Basen ausprobiert, denn wenn wenn n ist eine Pseudoprimin für eine Basis, dann scheint es eher ein Pseudoprime für eine andere Basis zu sein.^{[4]: §8}

Zum Testen willkürlich groß nEs ist wichtig, dass die Auswahl von Basen zufällig ausgewählt wird, da wir die Verteilung von Zeugen und starken Lügner unter den Zahlen 1, 2,…, nicht kennen, nicht kennen. n–1.^[b]

Ein vorgewählter Satz von einigen kleinen Basen garantiert jedoch die Identifizierung aller Verbundwerkstoffe bis zu einem vorbereiteten Maximum. Dieses Maximum ist im Vergleich zu den Basen im Allgemeinen ziemlich groß. Dies gibt sehr schnelle deterministische Tests für klein genug n (sehen Sektion Testen gegen kleine Sätze von Basen unter).

Beweise

Hier ist ein Beweis dafür, wenn n ist eine seltsame Prime, die einzigen Quadratwurzeln von 1 Modulo n sind 1 und -1.

Hier ist ein Beweis dafür, dass wenn n ist eine seltsame Primzahl, dann ist es eine starke wahrscheinliche Primzahl für die Basis a.

Beispiel

Angenommen, wir möchten feststellen, ob n= 221 ist Prime. Wir schreiben n–1 als 2²· 55, damit wir haben s= 2 und d= 55. Wir wählen zufällig eine Zahl aus a so dass 1 <a<n - 1, sagen Sie a = 174. Wir berechnen:

• a^20·d Mod n = 174⁵⁵ MOD 221 = 47 ≠ 1, n - 1
• a^21·d Mod n = 174¹¹⁰ Mod 221 = 220 = n - 1.

Seit 220 ≡ −1 mod n, entweder 221 ist Prime oder 174 ist ein starker Lügner für 221. Wir versuchen einen anderen zufälligen a, diesmal wählen Sie a = 137:

• a^20·d Mod n = 137⁵⁵ MOD 221 = 188 ≠ 1, n - 1
• a^21·d Mod n = 137¹¹⁰ MOD 221 = 205 ≠ n - 1.

Daher ist 137 ein Zeuge für die Kompositheit von 221, und 174 war tatsächlich ein starker Lügner. Beachten Sie, dass dies nichts über die Faktoren von 221 aussagt (die 13 und 17). Das Beispiel mit 341 in ein späterer Abschnitt zeigt, wie diese Berechnungen manchmal zu einem Faktor von führen können n.

Miller -Rabin -Test

Der Algorithmus kann geschrieben werden Pseudocode folgendermaßen. Der Parameter k bestimmt die Genauigkeit des Tests. Je größer die Anzahl der Runden ist, desto genauer ist das Ergebnis.

Eingabe Nr. 1: n > 3, eine seltsame Ganzzahl, die auf Primalität getestet werden mussEingabe #2: kdie Anzahl der Testrunden zur DurchführungAusgabe: "zusammengesetzt" wenn n wird als zusammengesetzt befunden, “Wahrscheinlich PrimeAnsonsten schreiben n als 2s·d + 1 mit d seltsam (durch Berücksichtigung von Kräften von 2 von n - 1) WitnessLoop: wiederholen k mal: Wählen Sie eine zufällige Ganzzahl aus a im Bereich [2, n - 2] x ← ad Mod n  wenn x = 1 oder x = n - 1 dann  fortsetzen WitnessLoop wiederholen s - 1 mal: x ← x2 Mod n  wenn x = n - 1 dann  fortsetzen WitnessLoop Rückkehr “zusammengesetzt”Rückkehr “Wahrscheinlich Prime”

Komplexität

Verwendung wiederholtes QuadratDie Laufzeit dieses Algorithmus ist O(k Protokoll³ n), wo n ist die auf Primalität getestete Zahl und k ist die Anzahl der durchgeführten Runden; Dies ist daher ein effizienter Polynom-Zeit-Algorithmus. Fft-basierte Multiplikation (Harvey-Hoeven-Algorithmus) kann die Laufzeit zu verkürzen, um Ö(k Protokoll² n Protokollprotokoll n) = Õ(k Protokoll² n).

Genauigkeit

Der Fehler, der durch den Primalitätstest gemacht wurde, wird an der Wahrscheinlichkeit gemessen, dass eine zusammengesetzte Zahl wahrscheinlich prim erklärt wird. Je mehr Stützpunkte a werden versucht, desto besser die Genauigkeit des Tests. Es kann gezeigt werden, dass wenn n ist zusammengesetzt, dann höchstens 1⁄4 der Basen a sind starke Lügner für n.^[2][6] Infolgedessen, wenn n ist zusammengesetzt und dann läuft k Iterationen des Miller -Rabin -Tests werden erklären n Wahrscheinlich mit einer Wahrscheinlichkeit höchstens 4 vorhanden^−k.

Dies ist eine Verbesserung gegenüber dem Solovay -Strassen -Test, deren schlimmster Fehler gebunden ist 2^−k. Darüber hinaus ist der Miller -Rabin -Test streng stärker als der Solovay -STRASS -Test in dem Sinne, dass für jeden Komposit n, die Reihe starker Lügner für n ist eine Untergruppe des Satzes von Euler Lügner zum nund für viele nDie Teilmenge ist richtig.

Darüber hinaus für große Werte von nDie Wahrscheinlichkeit, dass eine zusammengesetzte Zahl wahrscheinlich für Prime deklariert wird, ist oft signifikant kleiner als 4^−k. Zum Beispiel für die meisten Zahlen nDiese Wahrscheinlichkeit wird durch 8 begrenzt^−k; der Anteil der Zahlen n die diese Obergrenze ungültig machen, verschwindet, wenn wir größere Werte von betrachten n.^[7] Daher die Durchschnitt Fall hat eine viel bessere Genauigkeit als 4^−k, eine Tatsache, für die ausgenutzt werden kann Erstellen Wahrscheinliche Primzahlen (siehe unter). Solche verbesserten Fehlergrenzen sollten jedoch nicht darauf angewiesen werden verifizieren Primzahlen, deren Wahrscheinlichkeitsverteilung wird nicht kontrolliert, da a kryptografisch Der Gegner kann eine sorgfältig ausgewählte Pseudoprime senden, um den Primalitätstest zu besiegen.^[c] In solchen Kontexten nur die schlimmsten Fall Fehlergrenze von 4^−k kann sich darauf verlassen werden.

Das obige Fehlermaß ist die Wahrscheinlichkeit, dass eine zusammengesetzte Zahl als starke wahrscheinliche Primzahl deklariert wird k Testrunden; In mathematischen Worten ist es das bedingte Wahrscheinlichkeit ${\ displayStyle \ pr (m \! r_ {k} \ mid \ lnot p)}$ wo P ist der Veranstaltung dass die getestete Zahl vorrangiert ist und HERR_k ist das Ereignis, an dem es den Miller -Rabin -Test besteht k Runden. Wir sind oft an der inversen bedingten Wahrscheinlichkeit interessiert ${\ displayStyle \ pr (\ lnot p \ mid m \! r_ {k})}$: Die Wahrscheinlichkeit, dass eine Zahl, die als starke wahrscheinliche Primzahl deklariert wurde, tatsächlich zusammengesetzt ist. Diese beiden Wahrscheinlichkeiten sind von verwandt von Bayes 'Gesetz:

${\ displayStyle \ pr (\ lnot p \ mid m \! r_ {k}) = {\ frac {\ pr (\ lnot p \ land m \! r_ {k})} {\ pr (\ lnot p \ land M \! R_ {k})+\ pr (p \ land m \! R_ {k})}}} = {\ frac {1} {1+{\ frac {\ pr (m \! R_ {k} \ Mid p)} {\ pr (m \! r_ {k} \ mid \ lnot p)}} \ cdot {\ frac {\ pr (p)} {\ pr (\ lnot p)}}} = {\ \ FRAC {1} {1+{\ frac {1} {\ pr (m \! r_ {k} \ mid \ lnot p)}} \ cdot {\ frac {\ pr (p)} {1- \ pr ( P)}}}}}$

In der letzten Gleichung haben wir den Ausdruck unter Verwendung der Tatsache vereinfacht, dass alle Primzahlen korrekt als starke wahrscheinliche Primzahlen angegeben werden (der Test hat keine Falsch negativ). Durch fallen linker Teil des NennerWir leiten eine einfache Obergrenze ab:

${\ displayStyle \ pr (\ lnot p \ mid m \! r_ {k}) <\ pr (m \! r_ {k} \ mid \ lnot p) \ cdot \ links ({\ tfrac {1} {\ prpr (P)}}-1 \ rechts)}$

Daher hängt diese bedingte Wahrscheinlichkeit nicht nur mit der oben diskutierten Fehlermaßnahme zusammen, die durch 4 begrenzt ist^−k- aber auch zum Wahrscheinlichkeitsverteilung der Eingangsnummer. Im allgemeinen Fall wird diese Verteilung, wie bereits erwähnt, durch einen so unbekannten kryptografischen Gegner kontrolliert ${\ displayStyle \ pr (\ lnot p \ mid m \! r_ {k})}$. In dem Fall, wenn wir den Miller -Rabin -Test verwenden, um zu generieren Primzahlen (siehe unter), die Verteilung wird vom Generator selbst ausgewählt, sodass wir dieses Ergebnis ausnutzen können.

Deterministische Varianten

Miller -Test

Der Miller -Rabin -Algorithmus kann deterministisch gemacht werden, indem alles möglich ist a unter einer bestimmten Grenze. Einnahme n wie die Grenze implizieren würde Ö(n) Versuche, daher wäre die Laufzeit exponentiell in Bezug auf die Größe Protokoll n der Eingabe. Um die Laufzeit zu verbessern, besteht die Herausforderung darin, die Grenze so weit wie möglich zu senken und gleichzeitig den Test zuverlässig zu halten.

Wenn die getestete Nummer n ist zusammengesetzt, die starken Lügner a Coprime zu n sind in einem angemessenen Untergruppe aus der Gruppe (Z/nZ)*, was bedeutet, dass, wenn wir alle testen a von einem Set welches erzeugt (Z/nZ)*, einer von ihnen muss außerhalb der genannten Untergruppe liegen, daher muss ein Zeuge für die Kompositheit von sein n. Annahme der Wahrheit der Wahrheit der Generalisierte Riemann -Hypothese (GRH) Es ist bekannt, dass die Gruppe durch ihre Elemente erzeugt wird, die kleiner als Ö((ln n)²), was bereits von Miller bemerkt wurde.^[1] Die Konstante, die an der beteiligt ist Big O Notation wurde auf 2 von reduziert von Eric Bach.^[9] Dies führt zu dem folgenden deterministischen Primalitätstest -Algorithmus, der als die bekannt ist Miller -Test:

Eingang: n > 1, eine ungerade Ganzzahl, die auf Primalität getestet werden mussAusgabe: "zusammengesetzt" wenn n ist zusammengesetzt, “PrimeAnsonsten schreiben n als 2s·d + 1 mit d seltsam (durch Berücksichtigung von Kräften von 2 von n - 1) WitnessLoop: für alle a in der Bereich [2, min (n–2, ⌊2 (ln n)2⌋)]: x ← ad Mod n  wenn x = 1 oder x = n - 1 dann  fortsetzen WitnessLoop wiederholen s - 1 mal: x ← x2 Mod n  wenn x = n - 1 dann  fortsetzen WitnessLoop Rückkehr “zusammengesetzt”Rückkehr “Prime”

Die volle Kraft der verallgemeinerten Riemann -Hypothese ist nicht erforderlich, um die Richtigkeit des Tests zu gewährleisten: Da wir uns mit Untergruppen von selbst befassen IndexEs reicht aus, die Gültigkeit von GRH für anzunehmen quadratisch Dirichlet -Charaktere.^[6]

Die Laufzeit des Algorithmus ist in der Soft-o Notation, Õ ((Protokoll n)⁴) (Verwendung von FFT -basierten Multiplikation).

Der Miller -Test wird in der Praxis nicht verwendet. Für die meisten Zwecke die ordnungsgemäße Verwendung des probabilistischen Miller -Rabin -Tests oder des Baillie -PSW -Primalitätstest gibt ausreichend Vertrauen, während er viel schneller läuft. In der Praxis ist es auch langsamer als häufig verwendete Beweismethoden wie z. Apr-Cl und ECPP die Ergebnisse liefern, die nicht auf unbewiesenen Annahmen beruhen. Für theoretische Zwecke, die einen deterministischen Polynomzeitalgorithmus erfordern, wurde es von der ersetzt ASS -Primalitätstest, was auch nicht auf unbewiesene Annahmen beruht.

Testen gegen kleine Sätze von Basen

Wenn die Nummer n Testen zu werden ist klein, alle versuchen a < 2(ln n)² ist nicht notwendig, da viel kleinere Sätze potenzieller Zeugen bekannt sind. Zum Beispiel Pomerance, Selfridge, Wagstaff^[4] und Jaeschke^[10] habe das überprüft

• wenn n < 2,047, it is enough to test a = 2;
• wenn n < 1,373,653, it is enough to test a = 2 und 3;
• wenn n < 9,080,191, it is enough to test a = 31 und 73;
• wenn n < 25,326,001, it is enough to test a = 2, 3 und 5;
• wenn n < 3,215,031,751, it is enough to test a = 2, 3, 5 und 7;
• wenn n < 4,759,123,141, it is enough to test a = 2, 7 und 61;
• wenn n < 1,122,004,669,633, it is enough to test a = 2, 13, 23 und 1662803;
• wenn n < 2,152,302,898,747, it is enough to test a = 2, 3, 5, 7 und 11;
• wenn n < 3,474,749,660,383, it is enough to test a = 2, 3, 5, 7, 11 und 13;
• wenn n < 341,550,071,728,321, it is enough to test a = 2, 3, 5, 7, 11, 13 und 17.

Unter Verwendung der Arbeit von FEITSMA und Galway, die im Jahr 2010 alle Pseudoprimes der Basis 2 aufzählen, wurde dies erweitert (siehe Oeis:A014233) Mit dem ersten Ergebnis, das später verschiedene Methoden in Jiang und Deng unter Verwendung verschiedener Methoden angezeigt wird:^[11]

• wenn n < 3,825,123,056,546,413,051, it is enough to test a = 2, 3, 5, 7, 11, 13, 17, 19 und 23.
• wenn n < 18,446,744,073,709,551,616 = 2⁶⁴, es reicht aus, um zu testen a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 und 37.

Sorenson und Webster^[12] Überprüfen Sie die oben genannten und berechnen Sie genaue Ergebnisse für diese größeren als 64 -Bit -Ergebnisse:

• wenn n < 318,665,857,834,031,151,167,461, it is enough to test a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 und 37.
• wenn n < 3,317,044,064,679,887,385,961,981, it is enough to test a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 und 41.

Andere Kriterien dieser Art, oft effizienter (weniger Grundlagen erforderlich) als die oben gezeigten, existieren.^{[13][14][15][16]} Sie geben sehr schnelle deterministische Primalitätstests für Zahlen im entsprechenden Bereich ohne Annahmen.

Es gibt eine kleine Liste potenzieller Zeugen für jede mögliche Eingabegröße (höchstens b Werte für b-Bit -Zahlen). Für alle zusammengesetzten Zahlen reichen jedoch keine endliche Menge von Basen aus. Alford, Granville und Pomerance haben gezeigt, dass es unendlich viele zusammengesetzte Zahlen gibt n dessen kleinste Wompositess -Zeuge zumindest ist (ln n)^{1/(3ln ln ln n)}.^[17] Sie argumentieren auch heuristisch, dass die kleinste Zahl w so dass jede zusammengesetzte Zahl unten n hat einen Wompositessous -Zeugen weniger als w sollte in Ordnung sein Θ(Protokoll n Protokollprotokoll n).

Varianten zum Auffinden von Faktoren

Durch Einfügen größter gemeinsamer Teiler Berechnungen in den obigen Algorithmus können wir manchmal einen Faktor von erhalten n anstatt das nur zu bestimmen n ist zusammengesetzt. Dies geschieht zum Beispiel, wenn n ist eine wahrscheinliche Hauptbasis a aber keine starke wahrscheinliche Hauptbasis a.^{[18]: 1402} Wir können diesen Fall im Algorithmus durch Vergleich erkennen x in der inneren Schleife nicht nur zu –1, sondern auch zu 1.

Wenn bei einer Iteration 1 ≤ r < s der inneren Schleife entdeckt der Algorithmus, dass der neue Wert y = a^{d· 2r} Mod n ist also gleich 1, da er weiß, dass der vorherige Wert x = a^{d· 2s–1} wurde über ± 1 unterschieden, das können wir ableiten x ist eine quadratische Wurzel von 1, die weder 1 noch –1 ist. Da dies nicht möglich ist, wenn n ist Prime, das impliziert das n ist zusammengesetzt. Darüber hinaus:

• seit x² ≡ 1 (mod n), Wir wissen das n teilt x² - 1 = ((x - 1) (x + 1);
• seit x ≢ ± 1 (Mod n), Wir wissen das n teilt sich nicht x - 1 Noch x + 1.

Daraus schließen wir das ab A = GCD (x - 1, n) und B = GCD (x + 1, n) sind nicht triviale (nicht unbedingt Haupt-) Faktoren von n (in der Tat seitdem n ist seltsam, diese Faktoren sind Coprime und n = A·B). Wenn Factoring ein Ziel ist, können diese GCD -Berechnungen zu wenig zusätzlichen Rechenkosten in den Algorithmus eingefügt werden. Dies führt zum folgenden Pseudocode, bei dem der hinzugefügte oder geänderte Code hervorgehoben wird:

Eingabe Nr. 1: n > 3, eine seltsame Ganzzahl, die auf Primalität getestet werden mussEingabe #2: kdie Anzahl der Testrunden zur DurchführungAusgabe: ("mehrere von”, m) Wenn ein nicht trivialer Faktor m von n gefunden,         “zusammengesetzt" wenn n wird ansonsten zusammengesetzt, “Wahrscheinlich PrimeAnsonsten schreiben n als 2s·d + 1 mit d seltsam (durch Berücksichtigung von Kräften von 2 von n - 1) WitnessLoop: wiederholen k mal: Wählen Sie eine zufällige Ganzzahl aus a im Bereich [2, n - 2] x ← ad Mod n  wenn x = 1 oder x = n - 1 dann  fortsetzen WitnessLoop wiederholen s - 1 mal: y ← x2 Mod n  wenn y = 1 dann  Rückkehr ("mehrere von”, GCD (x - 1, n))  x ← y  wenn x = n - 1 dann  fortsetzen WitnessLoop Rückkehr “zusammengesetzt”Rückkehr “Wahrscheinlich Prime”

Das ist nicht ein probabilistisch Faktorisierung Algorithmus, weil es nur in der Lage ist, Faktoren für Zahlen zu finden n die pseudoprimieren sind, um zu basieren a (Mit anderen Worten für Zahlen n so dass a^n–1 ≡ 1 mod n). Für andere Zahlen gibt der Algorithmus nur zurück “zusammengesetztOhne weitere Informationen.

Zum Beispiel überlegen n = 341 und a = 2. Wir haben n - 1 = 85 · 4. Dann 2⁸⁵ Mod 341 = 32. und 32² Mod 341 = 1. Das sagt uns das n ist eine Pseudoprimebasis 2, aber keine starke Pseudoprimebasis 2. Durch Berechnen eines GCD in diesem Stadium finden wir einen Faktor von 341: GCD (32 - 1, 341) = 31. In der Tat, 341 = 11 · 31.

Um Faktoren häufiger zu finden, können die gleichen Ideen auch auf die Quadratwurzeln von –1 (oder eine andere Anzahl) angewendet werden. Diese Strategie kann implementiert werden, indem Wissen aus früheren Runden des Miller -Rabin -Tests ausnutzt. In diesen Runden haben wir möglicherweise ein Quadratwurzelmodulo identifiziert n von -1, sagen wir R. Dann wenn x² Mod n = n–1Wir können den Wert von vergleichen x gegen R: wenn x ist weder R Noch n−R, dann GCD (x − R, n) und GCD (x + R, n) sind nicht triviale Faktoren von n.^[13]

Erzeugung wahrscheinlicher Primzahlen

Der Miller -Rabin -Test kann verwendet werden, um starke wahrscheinliche Primzahlen zu erzeugen, indem sie einfach nach dem Zufallsprinzip an den Test zeichnen. Dieser Algorithmus endet Fast sicher (Bei jeder Iteration besteht die Möglichkeit, eine Primzahl zu zeichnen). Der Pseudocode zum Erzeugen b‐bisschen Starke wahrscheinliche Primzahlen (mit dem bedeutendsten Bit -Set) sind wie folgt:

Eingabe Nr. 1: bdie Anzahl der Bits des ErgebnissesEingabe #2: kdie Anzahl der Testrunden zur DurchführungAusgabe: Eine starke wahrscheinliche Primzahl n während Richtig: Wählen Sie eine zufällige ungerade Ganzzahl n im Bereich [2b–1, 2b–1] wenn Der Miller -Rabin -Test mit Eingaben n und k kehrt zurück "Wahrscheinlich Prime” dann  Rückkehr n 

Komplexität

Natürlich die Worst-Case-Laufzeit ist unendlich, da die äußere Schleife möglicherweise nie endet, aber das geschieht mit Wahrscheinlichkeit Null. Gemäß Geometrische Verteilung, das erwartet Anzahl der Ziehungen ist ${\ displaystyle {\ tfrac {1} {\ pr (m \! r_ {k})}}}}$ (Wiederverwendung von Notationen von vorhin).

Da jede Primzahl den Test besteht, gibt die Wahrscheinlichkeit, dass die Primzahl ist, eine grobe Untergrenze für die Wahrscheinlichkeit, den Test zu bestehen. Wenn wir ungerade ganze Zahlen zeichnen gleichmäßig im Bereich [2^b–1, 2^b–1], dann bekommen wir:

$oder } \ rechts)} {2^{B-2}}}}$

wobei π das ist Prime-Counting-Funktion. Mit an ein Asymptotische Expansion von π (eine Verlängerung der Primzahl Theorem), wir können diese Wahrscheinlichkeit annähern, wenn b wächst in Richtung Unendlichkeit. Wir finden:

$oder$

$oder }$

Daher können wir erwarten, dass der Generator nicht mehr Miller -Rabin -Tests durchführt als eine Zahl proportional zu b. Unter Berücksichtigung der schlimmsten Komplexität jedes Miller-Rabin-Tests (siehe vorhin) Die erwartete Laufzeit des Generators mit Eingängen b und k wird dann von begrenzt von Ö(k b⁴) (oder Ö(k b³) Verwenden von FFT-basierter Multiplikation).

Genauigkeit

Das Fehlermaß dieses Generators ist die Wahrscheinlichkeit, dass er eine zusammengesetzte Zahl ausgibt.

Unter Verwendung der Beziehung zwischen bedingten Wahrscheinlichkeiten (gezeigt in einem früherer Abschnitt) und das asymptotische Verhalten von ${\ displayStyle \ pr (p)}$ (Kurz zuvor gezeigt), kann diese Fehlermessung eine grobe Obergrenze erhalten:

${\ displayStyle \ pr (\ lnot p \ mid m \! r_ {k}) <\ pr (m \! r_ {k} \ mid \ lnot p) \ cdot \ links ({\ tfrac {1} {\ prpr (P)}}-1 \ rechts) \ leq 4^{-k} \ cdot \ links ({\ tfrac {\ ln 2} {2} b-1+{\ mathcal {o}} \ links (b (b) ^{-1} \ rechts) \ rechts).}$

Daher für groß genug bDiese Fehlermessung ist geringer als ${\ displaystyle {\ tfrac {\ ln 2} {2} \ \ cdot b \ cdot 4^{-k}}$. Es gibt jedoch viel bessere Grenzen.

Verwenden Sie die Tatsache, dass der Miller -Rabin -Test selbst häufig einen Fehler aufweist, der viel kleiner als 4 ist^−k (sehen vorhin), Damgård, Landrock und Pomeranz Abgeleitete mehrere Fehlergrenzen für den Generator mit verschiedenen Parameternklassen b und k.^[7] Diese Fehlergrenzen ermöglichen es einem Implementierer, eine vernünftige Auswahl zu wählen k für eine gewünschte Genauigkeit.

Eine dieser Fehlergrenzen ist 4^−k, was für alle gilt b ≥ 2 (die Autoren zeigten es nur für b ≥ 51, während Ronald Burthe Jr. den Beweis mit den verbleibenden Werten 2 ≤ abgeschlossen hat b ≤ 50^[19]). Auch diese einfache gebundene kann für große Werte von verbessert werden b. Zum Beispiel ist eine andere von denselbe Autoren abgeleitete gebundene gebundene:

$oder$

das gilt für alle b ≥ 21 und k ≥ b⁄4. Diese Grenze ist kleiner als 4^−k sobald b ≥ 32.

Anmerkungen

Verweise

Externe Links

• Weisstein, Eric W. "Rabin-Miller Starker Pseudoprimetest". Mathord.
• Interaktive Online -Implementierung der deterministischen Variante (Schritt für Schritt durch den Algorithmus)
• Applet (Deutsch)
• Miller -Rabin -Primalitätstest in C#
• Müller -Rabin -Primalitätstest im JavaScript unter Verwendung beliebiger Präzisionsarithmetik