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.

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 mit .

oder auch:

Für alle Primzahlen p gilt mit .

Beispiel: p = 5 ist eine Primzahl

Gegenbeispiel: p = 55 ist keine Primzahl, denn für n = 2 gilt:

 ungleich 1

Das bedeutet, das die Zahl p = 55 ist keine Primzahl ist.

Würde für alle natürlichen Zahlen q mit q > 2 folgende Formel gelten:

Wenn jetzt zutreffen würde, dass q dann auch eine Primzahl ist, dann hätte man ein prima Verfahren zum Testen auf Primzahlen. Dass dem nicht so ist, daran sind die Pseudoprimzahlen schuld.

Pseudoprimzahlen

Es gibt Zahlen q, die keine Primzahlen sind und für die dennoch gilt:

nq - 1 - 1 durch q teilbar für bestimmte natürlichen Zahlen n < q, bei denen n kein Teiler von q ist.

Solche Zahlen heißen Pseudoprimzahlen.

Beispiel: q = 21 ist eine Pseudoprimzahl, da für n = 13 gilt

obwohl 21 eine zusammengesetzte Zahl der Form 3*7 ist.

Carmichael-Zahlen

Besonders hartnäckige Pseudoprimzahlen sind dabei die Carmichael-Zahlen, für die gilt, das alle Basen n mit 1 < n < q, die nicht Teiler von q sind:

 (für alle n teilerfremd zu q)

Als Beispiel dafür die 561 (sie ist die kleinste Carmichael-Zahl):

Basis 3: 

Basis 11: 

Auch für die Basen 17, 33, 51 und 187, die alle Teiler von 561 sind, gilt, das die Zahl 561 keine Primzahl ist.
Für alle anderen Basen, die keine Teiler von 561 sind, gilt:

Was kann man tun wenn man 100% sichere Ergebnisse bekommen will

Wenn man nur auf die Basis 2 testet, dann kann man nur bis 340 sicher sein, das man zu 100% ein korrektes ergebnis kommt. Wenn man parallel auf mehrere Basen (zum Beispiel 2, 3 und 5) testet, erhöht sich die sichere Grenze nach oben:

Bei 2 und 3 liegt die sichere Grenze bei 2700, bei 2,3,5,7 und 11 liegt sie bei 29340, und bei 2, 3, 5, 7, 11 und 13 liegt sie bei 162401. Leider macht jede weitere Basis ein Programm langsamer. Wenn man konsequent auf alle Basen testet, bekommt man zwar ein Programm, das zu 100% sichere Primzahlen zurückliefert, aber viel langsamer als ein Program ist, das eine Zahl konsequent auf alle möglichen Teiler testet.

Quellcode

Der Weg zum propabilistischen Primzahltest

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.

Dabei gibt es zwei Aspekte:

Suche mit nur einer Basis, bei zufälliger Auswahl der zu testenden Zahl

Wenn man nur eine Basis nimmt, vorzugsweise die Basis 2, dann hat man eine relativ geringe Wahrscheinlichkeit, aber den Umstand, dass wenn man schon fälschlich eine Pseudoprimzahl wie 341 trifft, dass diese zu 100% falsch ist, auch wenn die Wahrscheinlichkeit auf die 341 zu treffen nur gering ist. Jedesmal, wenn man auf 341 prüft, wird der kleine Fermatsche Satz in der Kombination mit 341 und Basis 2 das Urteil "Primzahl" zurückgeben.

Wenn man, anstelle von auf und prüft, hat man zwar statt einem Fall zwei Fälle zu unterscheiden, aber die Zahl der möglichen Pseudoprimzahlen veringert sich.

Breitensuche mit zufälliger Auswahl einer oder mehrerer Basen (mit möglicher zufälliger Auswahl, der zu testenden Zahl)

Der andere Aspekt ist die Prüfung in der Breite. Bezogen auf die 68 möglichen Primzahlbasen, liefern 21 Primbasen für die 341 fälschlich das Ergebnis "Primzahl" zurück. Das ist ein bisschen weniger als 1/3.

Hier würde eine Verwendung der Eulerschen Formel anstelle des kleinen Fermat zu einer Verringerung der fälschlich zurückliefernden Primbasen führen. Wo beim kleinen Fermat zur Pseudoprimzahl 91 noch 8 Primbasen (3, 17, 23, 29, 43, 53, 61 und 79) fälschlich eine Primzahl melden, sind es bei der Eulerschen Formel noch die Hälfte (17, 29, 53 und 79). Das verbessert einen propabilistischen Ansatz erheblich.

Im Fall der Carmichael-Zahl 561 lügen 99 von 102 Primzahlbasen. Bei größeren Carmichaelzahlen, die oft aus nicht viel mehr Primfaktoren zusammengesetzt sind, wird das Missverhältnis noch extremer. Darum vermeiden bessere propabilistische Primzahltests das Problem der Carmichael-Zahlen.

Hier eine Tabelle von besonders guten Pseudoprimzanlen (die keine Carmichael-Zahlen sind). Die 15 ist aufgeführt, weil sie die erste Pseudoprimzahl ist, und die 91 ist in ihrer Umgebung eine relativ gute Pseudoprimzahl.

A: Anzahl der Primzahlen zwischen 2 und der entsprechenden Pseudoprimzahl

B: Anzahl der Primzahlen aus A die fälschlich behaupten, die entsprechende Pseudoprimzahl sei eine Primzahl

C: Die Wahrscheinlichkeit, bei Auswahl einer Primzahlbasis eine der nicht lügenden zu erwischen

Bei den Carmichael-Zahlen geht die Wahrscheinlichkeit, eine der nichtlügenden Primzahlbasen zu erwischen gegen 0.

Wenn man zufällig mehrere Primzahlbasen auswählt, dann steigt die Wahrscheinlichkeit, Pseudoprimzahlen als solche zu entlaven:

Anzahl der testenden Primzahlbasen

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 so genannten Miller-Rabin-Test. Nicht-Primzahlen erkennt er mit Sicherheit, Primzahlen mit Wahrscheinlichkeit 1/2. Eine k-malige Widerholung des Tests verringert die Irrtumswahrscheinlichkeit auf 1/2^k.

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

• C.Pomerance,J.L.Selfridge, S.S.Wagstaff Jr., "The pseudoprimes to 25 · 109," Math. Comp., 35:151 (1980) 1003-1026.
• Paolo Ribenboim, The new Book of Prime Number Records, (1996) Springer Verlag