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 n^p-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 (n^p-1 -1)mod p = 0 mit n < p.

oder auch:

Für alle Primzahlen p gilt (n^p-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:

n^q-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 n^p-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 n^p-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.

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.