Fermatscher Primzahltest
Mit dem Fermatschen Primzahltest - entwickelt von dem "Freizeitmathematiker" Pierre de Fermat - kann man aussagen, ob eine Zahl mit hoher Wahrscheinlichkeit eine Primzahl ist.
Anwendung des Kleinen Fermatschen Satzes
Direkt aus dem Kleinen Fermatschen Satz folgt:
- Ist p eine Primzahl, dann ist np-1 -1 durch p teilbar für alle natürlichen Zahlen n < p.
Dies kann man mit Hilfe der Modulo-Funktion schreiben als:
- Für alle Primzahlen p gilt (np-1 -1)mod p = 0 mit n < p.
oder auch:
- Für alle Primzahlen p gilt (np-1)mod p = 1 mit n < p.
Beispiel: p = 5 ist eine Primzahl
n=1: 15-1 -1 = 0 ist teilbar durch 5
n=2: 25-1 -1 = 15 ist teilbar durch 5
n=3: 35-1 -1 = 80 ist teilbar durch 5
n=4: 45-1 -1 = 255 ist teilbar durch 5
Carmichael-Zahlen
Es gibt allerdings auch Zahlen q, die keine Primzahlen sind und für dennoch gilt:
- nq-1 -1 durch q teilbar für alle natürlichen Zahlen n < q.
Solche Zahlen heissen Carmichael-Zahlen.
Dies Zahlen sind benannt nach dem amerikanischen Mathemetiker R.D.Carmichael (1879 - 1967).
Zwar gibt es unendlich viele Carmichael-Zahlen, aber im Vergleich zur Anzahl der Primzahlen sind es sehr wenige. Unter 100.000 gibt es nur die folgenden 16 Carmichael-Zahlen: 561 (=3·11·17), 1105, 1729 (=7·13·19), 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, and 75361. Man kann zeigen: Jede Carmichael-Zahl hat mindestens 3 Primfaktoren.
Aus dem obigen Satz folgt sofort die folgende Aussage:
- Findet man eine natürliche Zahl n < p mit der Eigenschaft np-1 -1 ist nicht durch p teilbar, dann ist p keine Primzahl.
Beispiel: p = 21 ist keine Primzahl, denn für n = 2 gilt
221-1mod 21 = 220mod 21 = ((210mod 21)2)mod 21 = 4 ungleich 1, d.h. p = 21 ist keine Primzahl.
Fermatscher Primzahltest
Leider kann man mit den Regeln der Aussagenlogik nicht die Umkehrung herleiten, aber es gilt die folgende Regel, der sogenannte Fermatsche Primzahltest:
- Wenn np-1 -1 durch p teilbar für alle natürlichen Zahlen n < p, dann ist p mit hoher Wahrscheinlichkeit eine Primzahl.
Der Test weist nämlich fälschlicherweise auch jede Carmichael-Zahl als Primzahl aus. Da diese jedoch - wie oben beschrieben - sehr selten auftreten, ist die Fehlerwahrscheinlichkeit des Primzahltests gering.
Eine absolute Sicherheit wird allerdings durch die Carmichael-Zahlen verhindert.
Pseudo-Primzahlen
Man kann nun versuchen, diesen Test zu vereinfachen und den Rechenaufwand deutlich zu reduzieren, wenn man eine etwas geringere Wahrscheinlichkeit in der Primzahlaussage in Kauf nimmt.
Dazu folgende Definition:
- Eine natürliche Zahl p heisst Pseudo-Primzahl zur Basis a bzw. pseudoprim zur Basis a, wenn ap-1 -1 durch p teilbar und die natürliche Zahl a < p ist.
- Findet man eine Zahl a < p, zu deren Basis p nicht pseudoprim ist, dann ist p keine Primzahl, was direkt aus dem Kleinen Fermatschen Satz folgt.
- Ist p zu jeder Basis a < p pseudoprim, dann ist p entweder eine Primzahl oder eine Carmichael-Zahl.
- Ist p pseudoprim zur Basis a, dann könnte p eine Primzahl sein. Man sagt auch, die Zahl a sei ein Zeuge dafür, dass p eine Primzahl ist. Findet man weitere Zahlen zu deren Basis p pseudoprim ist, dann hat man weitere Zeugen dafür, dass p eine Primzahl ist. D.h. die Wahrscheinlichkeit steigt, dass p eine Primzahl ist.
Es gibt relativ wenig Zahlen p, die nicht prim sind aber dennoch pseudoprim zu einer Basis a.
Beispiel: p = 341 = 31·11 ist pseudoprim zur Basis 2, denn 2341-1 -1 ist teilbar durch 341.
C.Pomerance, J.L.Selfridge und S.S.Wagstaff Jr. zeigten im Jahre 1980, dass es unterhalb von 25.000.000.000 zwar 1.091.987.405 Primzahlen, aber nur 21.853 Pseudo-Primzahlen zur Basis 2 gibt.
Daraus folgt:
- Ist p pseudoprim zur Basis 2, dann ist p mit hoher Wahrscheinlichkeit eine Primzahl.
Für die Praxis bedeutet das: Oft reicht der Nachweis aus, dass p pseudoprim ist zur Basis 2. Will man die Sicherheit weiter erhöhen, dann muss man eben weitere Zeugen finden, d.h. weitere Zahlen a, zu deren Basis p pseudoprim ist.
Im Grenzfall testet man alle Zahlen a < p, d.h. man führt den gesamten Fermattest durch.
Verbesserungen des Fermatschen Primzahltests
Gary Miller und Michael O.Rabin verbesserten den Fermattest im sogenannten Rabin-Miller-Test. Nicht-Primzahlen erkennt er mit doppelter Wahrscheinlichkeit.
Im Jahre 1980 stellten die Mathematiker L.M. Adleman, R.S. Rumely, H. Cohen und H.W. Lenstra Jr den nach ihnen benannten ARCL-Test vor. Dieser ist eine Weiterentwicklung des Fermatschen Primzahltests, indem er Carmichael-Zahlen erkennt.
Literatur
- C.Pomerance,J.L.Selfridge, S.S.Wagstaff Jr., "The pseudoprimes to 25 · 109," Math. Comp., 35:151 (1980) 1003-1026.