Lösung - Primzahlen 06

Miller-Rabin-Primzahltest

Der Miller-Rabin-Test ist ein starker (probabilistischer) Primzahltest, der 1980 von Michael O. Rabin auf Basis von Ergebnissen von Gary. L. Miller veröffentlicht wurde.

Dieser Primzahlen-Test ermöglicht es, Primzahlen in einer Größenordnung bis zu 10^1000 innerhalb kürzester Zeit zu berechnen. Wenn man noch höher hinaus will, nimmt die Rechenzeit allerdings deutlich zu.

Während jene Zahlen, die den Test nicht bestehen, mit Sicherheit nicht prim sind, kann für die gefundenen Primzahlen nur eine Wahrscheinlichkeitssausage getroffen werden. Man nennt sie daher "pseudoprim".

Die Wahrscheinlichkeit, dass eine derartig gefundene Pseudoprimzahl doch Teiler hat, ist jedoch bei hinreichender Wiederholung des Tests sehr klein, man spricht daher auch von starken Pseudoprimzahlen. Die meisten Computeralgebrasysteme verwenden auch den Miller-Rabin-Test für ihre Primzahlüberprüfung.

Mathematische Grundlage

ist wieder der kleine Satz von Fermat.
(Sei n eine Primzahl, dann gilt: an-1 mod n = 1 für alle a aus [1, n-1]).

Die weitere Zutat des Miller-Rabin-Tests ist folgender Satz:

Satz: Wenn n eine Primzahl ist, dann hat die quadratische Gleichung x2 mod n = 1 nur die beiden Lösungen x = 1 und x = -1.
Gibt es eine weitere Lösung x, dann ist n keine Primzahl. Findet man also ein x ungleich 1 oder -1 mit x2 mod n = 1, so spricht man von einer nichttrivialen Quadratwurzel von 1 mod n.

Der Primzahlen-Test besteht nun darin, zu der zu prüfenden Zahl n eine Zahl a (einen "Zeugen") zu finden, mit der unter Zuhilfenahme des Fermattests und unter Überprüfung des Vorliegens einer nichttrivialen Quadratwurzel gezeigt werden kann, dass n keine Primzahl ist - in einer Kombination der beiden Bedingungen.
Mit entsprechenden mehrmaligen Durchläufen / Zeugen (zufällig gewählt) kann die Wahrscheinlichkeit, dass eine Primzahl vorliegt, sehr hoch geschraubt werden.

Tipp: Wenn man viele Zahlen untersuchen möchte oder sehr große Zahlen betrachtet, empfiehlt es sich, zunächst die ersten möglichen Primfaktoren (aus einer vorher erstellten Liste) "abzuklopfen" und erst dann über den Miller-Rabin-Test vorzugehen - Grund: für kleine Primfaktoren ist das Verfahren zu langsam.

Beispiele:
Wir wollen überprüfen, ob das zusätzliche Kriterium Zahlen, die den Fermattest bestehen und trotzdem keine Primzahlen sind (= Carmichaelzahlen) ausfiltert. Wir betrachten zu diesem Zweck die ersten beiden Carmichaelzahlen 561 und 1105 und wählen als Zeugen a = 2.

n = 561, n-1 = 560
a = 2
560 = 16 * 35 = 2^4 * 35

wir betrachten 235 (erster Teiler 35) und quadrieren 4 mal (zweiter Teiler 16 = 24).

  2^35 mod 561 = 263
263^ 2 mod 561 = 166
166^ 2 mod 561 =  67
 67^ 2 mod 561 =   1

Damit gibt es aber eine nichttriviale Quadratwurzel. n = 561 ist also keine Primzahl.

n = 1105, n-1 = 1104
a = 2
1104 = 2^4 * 3 * 23

wir betrachten 269 (erster Teiler 3*23=69) und quadrieren 4 mal (zweiter Teiler 16 = 24).

  2^69 mod 1105 = 967
967^ 2 mod 1105 = 259
259^ 2 mod 1105 = 781
781^ 2 mod 1105 =   1

Damit gibt es aber wieder eine nichttriviale Quadratwurzel. Auch n = 1105 ist keine Primzahl.


[ Schliessen ]