Mit dem Fermatschen Primzahltest - entwickelt von dem "Freizeitmathematiker" Pierre de Fermat - kann man aussagen, ob eine Zahl mit hoher Wahrscheinlichkeit eine Primzahl ist. Daher wird dieses Verfahren auch PRP-Test (= probable prime) genannt.

Table of contents

1 Anwendung des Kleinen Fermatschen Satzes 2 Carmichael-Zahlen 3 Fermatscher Primzahltest 4 Pseudo-Primzahlen 5 Verbesserungen des Fermatschen Primzahltests 6 Literatur

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.

Für alle Primzahlen p gilt (n^p-1 -1)mod p = 0 mit n < p.

Für alle Primzahlen p gilt (n^p-1)mod p = 1 mit n < p.

         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

Zwar gibt es unendlich viele Carmichael-Zahlen (das ist seit 1992 bekannt), 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.

Weitere Eigenschaften von Carmichael-Zahlen:

• Jede Carmichael-Zahl hat mindestens 3 Primfaktoren.
• Unter den Teilern einer Carmichael-Zahl ist keine Quadratzahl.
• Sei n eine Carmichael-Zahl, p ein Primteiler von n. Dann ist (n-1) durch (p-1) teilbar.
• Sei p > 3 eine Primzahl derart, dass auch 2p-1 und 3p-2 Primzahlen sind, dann ist n = p(2p-1)(3p-2) eine Carmichael-Zahl. Beispiel: p=7 --> n=7·13·19=1729.

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.

221-1mod 21 = 220mod 21 = ((210mod 21)2)mod 21 = 4 ungleich 1, d.h. p = 21 ist keine Primzahl.

Leider kann man mit den Regeln der Aussagenlogik nicht die Umkehrung herleiten, aber es gilt die folgende Regel, der so genannte 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.

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 heißt Pseudo-Primzahl zur Basis a bzw. pseudoprim zur Basis a, wenn a^p-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.

Beispiele: p = 341 = 31·11 ist pseudoprim zur Basis 2, denn 2^341-1 -1 ist teilbar durch 341. (Dieses Beispiel entdeckte P.F.Sarrus im Jahr 1819.) Der Nachweis ist mit Methoden der Restklassen vergleichsweise einfach. In dem Artikel Restklassen wird dieser Nachweis als Anwendungsbeispiel demonstriert.

Auch p = 91 = 7·13 ist pseudoprim zur Basis 3, denn 3^91-1 -1 ist teilbar durch 91.

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.

Verbesserungen des Fermatschen Primzahltests

Gary Miller und Michael O.Rabin verbesserten den Fermattest im so genannten Rabin-Miller-Test. Nicht-Primzahlen erkennt er mit doppelter Wahrscheinlichkeit.

Im Jahre 1980 stellten die Mathematiker Leonard 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