Fermat-Test

Der Fermat-Test zur Basis $a$ basiert auf dem Kleinen Satz von Fermat. Wir testen also für eine Zahl ob

gilt (zum Beispiel mit der Square-And-Multiply-Methode). Ist dies der Fall, dann kann die Zahl $p$ eine Primzahl sein.

Leider ist es aber möglich, dass auch eine zusammengesetzte Zahl diese Kongruenzgleichung erfüllt. Diese Zahlen nennt man auch Pseudoprimzahl.

Es fällt allerdings auf, dass die Anzahl an Pseudoprimzahlen im Vergleich zu echten Primzahlen sehr gering ist.

Wir schätzen die Anzahl der Primzahlen kleiner gleich $x$ mit

Damit gilt dann nach Erdös:

Eine Zahl, die einen oder mehrere Tests (zu unterschiedlichen Basen) besteht, nennt man auch eine wahrscheinliche Primzahl. Normalerweise testet man vorher mit den bereits genannten Methoden auf kleine Teiler und nutzt dann einen Primzahltest wie den Fermattest auf den übrig gebliebenen Zahlen.

Ein Problem dieses Tests sind sogenannte Carmichael-Zahlen, die für alle Basen den Test bestehen obwohl sie Pseudoprimzahlen sind.