Fermat- und Miller-Rabin-Einfachheitstests

Gruß an die Bürger von Habrovsk! Wir teilen auch heute noch nützliches Material, dessen Übersetzung speziell für Studenten des Kurses "Algorithmen für Entwickler" erstellt wurde .



Wie kann man angesichts einer Zahl n verstehen, dass diese Zahl eine Primzahl ist? Angenommen, n anfänglich ungerade, weil die Aufgabe sonst recht einfach ist.

Die naheliegendste Idee wäre jedoch, nach allen Teilern von n zu suchen. Bisher besteht das Hauptproblem darin, einen effizienten Algorithmus zu finden.

---

Farm Test

Nach dem Satz von Fermat gilt , wenn n eine Primzahl ist, für jedes a die folgende Gleichheit: a n−1 =1 (mod n) . Hieraus können wir die Fermat-Testregel ableiten, um die Einfachheit einer Zahl zu überprüfen: nimm ein zufälliges a ∈ {1, ..., n−1} und überprüfe, ob die Gleichheit a n−1 =1 (mod n) gilt. Wenn die Gleichheit nicht beachtet wird, ist n höchstwahrscheinlich zusammengesetzt.

Trotzdem kann die Gleichheitsbedingung erfüllt werden, auch wenn n nicht einfach ist. Nehmen n = 561 = 3 × 11 × 17 zum Beispiel n = 561 = 3 × 11 × 17 . Nach dem chinesischen Restsatz :

Z 561 = Z 3 × Z 11 × Z 17

, wobei jedes a ∈ Z ^∗ ₅₆₁ dem Folgenden entspricht:

(x,y,z) ∈ Z ∗ 3 ×Z ∗ 11 11×Z ∗ 17 .

Nach dem Satz von Fermat ist x 2 =1 , y 10 =1 z 16 =1 . Da 2, 10 und 16 alle 560 Teiler sind, bedeutet dies, dass (x,y,z) 560 = (1, 1, 1) , mit anderen Worten, a 560 = 1 für jedes a ∈ Z ∗ 561 .

Es spielt keine Rolle, für welches a wir uns entscheiden, 561 besteht den Fermat-Test trotz der Tatsache, dass es zusammengesetzt ist, immer, solange a mit n einfach ist. Solche Zahlen werden Carmichael-Zahlen genannt und es stellt sich heraus, dass es eine unendliche Anzahl von ihnen gibt.

Wenn a nicht mit n übereinstimmt, besteht es den Fermat-Test nicht. In diesem Fall können wir die Tests jedoch ablehnen und weiter nach den Teilern von n suchen und die GCD ( a, n ) berechnen.

Miller-Rabin-Test

Wir können den Test verbessern, indem wir sagen, dass n genau dann Primzahl ist, wenn die Lösungen x 2 = 1 (mod n) x = ±1 .

Wenn n den Fermat-Test besteht, a n−1 = 1 , dann prüfen wir auch, dass a (n−1)/2 = ±1 , da a (n−1)/2 die Quadratwurzel von 1 ist.

Leider können Zahlen wie zum Beispiel 1729 - die dritte Carmichael-Zahl - diesen verbesserten Test noch täuschen. Was ist, wenn wir iterieren? Das heißt, bis dies möglich ist, werden wir den Exponenten um die Hälfte reduzieren, bis wir eine andere Zahl als 1 erreichen. Wenn wir am Ende etwas anderes als -1 erhalten, wird n zusammengesetzt.

Genauer gesagt sei 2 ^S die größte Potenz von 2, die durch n-1 teilbar ist, n−1=2 S q für eine ungerade Zahl q . Jede Nummer aus der Sequenz

a n−1 = a (2^S)q , a (2^S-1)q , ..., aq .

Dies ist die Quadratwurzel des vorherigen Mitglieds der Sequenz.

Wenn n dann eine Primzahl ist, muss die Sequenz mit 1 beginnen und jede nachfolgende Zahl muss auch 1 sein, oder das erste Mitglied der Sequenz darf nicht 1 sein, aber dann ist es -1.

Der Miller-Rabin-Test nimmt ein zufälliges a∈ Z n . Beginnt die obige Folge nicht mit 1 oder ist das erste Glied der Folge nicht 1 oder -1, so ist n nicht einfach.

Es zeigt sich, dass für jedes zusammengesetzte n , einschließlich Carmichael-Zahlen, die Wahrscheinlichkeit, den Miller-Rabin-Test zu bestehen, ungefähr 1/4 beträgt. (Im Durchschnitt viel weniger.) Daher nimmt die Wahrscheinlichkeit, dass n mehrere Testläufe besteht, exponentiell ab.

Wenn n den Miller-Rabin-Test mit einer Sequenz, die mit 1 beginnt, nicht besteht, haben wir eine nicht-triviale Quadratwurzel von 1 modulo n und können die Teiler von n effizient finden . Daher lassen sich Carmichael-Zahlen immer bequem faktorisieren.

Wenn der Test auf Zahlen der Form pq angewendet wird, bei denen p und q große Primzahlen sind, bestehen sie den Miller-Rabin-Test in fast allen Fällen nicht, da die Sequenz nicht mit 1 beginnt. Daher können wir den RSA nicht knacken.

In der Praxis wird der Miller-Rabin-Test wie folgt durchgeführt:

1. Wenn n , müssen wir s so finden, dass n – 1 = 2 S q für ein ungerades q .
2. Nimm ein zufälliges a ∈ {1,...,n−1}
3. Wenn a ^q = 1 ist, besteht n den Test und wir stoppen die Ausführung.
4. Überprüfen Sie für i= 0, ... , s−1 die Gleichheit a (2^i)q = −1 . Wenn die Gleichheit gilt, besteht n den Test (Ausführung stoppen).
5. Wenn keine der obigen Bedingungen erfüllt ist, ist n zusammengesetzt.

Vor der Durchführung des Miller-Rabin-Tests ist es sinnvoll, noch ein paar unbedeutende Einteilungen in kleine Primzahlen vorzunehmen.

Streng genommen handelt es sich bei diesen Tests um Tests, um festzustellen, ob eine Zahl als zusammengesetzt angesehen wird, da sie zwar nicht beweisen, dass es sich bei der zu überprüfenden Zahl um eine Primzahl handelt, aber definitiv beweisen, dass sie sich als zusammengesetzt herausstellen kann.

Es gibt immer noch deterministische Algorithmen, die in der Polynomzeit arbeiten, um die Einfachheit zu bestimmen (Agrawal, Kayal und Saxena ), aber heute werden sie als unpraktisch angesehen.