Fermatscher Primzahltest

Der fermatsche Primzahltest ist ein Primzahltest, der auf dem kleinen fermatschen Satz beruht. Er dient dazu, Primzahlen von zusammengesetzten Zahlen zu unterscheiden.

Fermatscher Primzahltest

Der fermatsche Primzahltest beruht auf dem kleinen fermatschen Satz:
Für jede Primzahl und jede dazu teilerfremde natürliche Zahl ist folgende Kongruenz erfüllt:

.

Durch Umkehrung dieser Bedingung kann man für natürliche Zahlen testen, ob sie zusammengesetzt sind. Ist nämlich für eine zu teilerfremde Basis nicht durch teilbar, so kann nicht prim sein. Zum Beispiel kann man aus schließen, dass die Zahl zusammengesetzt ist.

Der fermatsche Primzahltest verläuft so:

  • Eingabe: , die zu testende natürliche Zahl, Ergebnis: zusammengesetzt oder keine Aussage
  • Wähle eine Basis mit aus. Prüfe, ob und teilerfremd sind.
Wenn sie nicht teilerfremd sind, dann ist das Ergebnis zusammengesetzt. Ansonsten:
Wenn , dann ist das Ergebnis zusammengesetzt.
Sonst ist das Ergebnis keine Aussage

Wird der Test mehrfach mit unterschiedlichen Basen wiederholt, so ist keine Aussage interpretierbar als vermutlich Primzahl.