Hintergrundwissen
FERMAT'scher Primzahltest
Auf Pierre de Fermat (1601-1665) geht eine Beobachtung zurück, die wir heute als Kleine Satz von Fermat bezeichnen. Diser Satz ist die theoretische Grundlage des FERMATschen Primzahltest.
Im FERMATschen Primzahltest überprüft man mit geeigneter Basis a, ob eine natürliche Zahl n die Bedingungan-1 = 1 (mod n) (*)
erfüllt. Wenn Sie die Bedingung erfüllt, ist sie wahrscheinlich prim zur Basis a, wenn sie die Bedingung nicht erfüllt, ist sie auf jeden Fall zusammengesetzt und kann daher keine Primzahl sein.
Der FERMATsche Primzahltest liefert deshalb nur das Ergebnis: vielleicht eine Primzahl oder keine Primzahl. Dennoch bietet er zwei Vorteile:
- Die Kongruenz an-1(mod n) ist numerisch schnell ermittelt
- Der Fehler (n ist keine Primzahl, sondern eine Pseudoprimzahl) ist relativ klein.
Überprüft man die Bedingung (*) mit mehrern Basen, so lässt sich der Fehler eine Pseudoprimzahl zu erwischen weiter einschränken. Es gibt nur drei Pseudoprimzahlen unter 100.000, die 2-PRP, 3-PRP, 5-PRP und 7-PRP sind:
29341, 46657, 75361