3. Elementare Zahlentheorie

E Primzahltest

Fermatscher Primzahltest

Der fermatsche Primzahltest beruht auf dem kleinen fermatschen Satz:

Für jede Primzahl p und jede dazu teilerfremde natürliche Zahl a ist folgende Kongruenz erfüllt:

ap−1 ≡ 1 mod p

Durch Umkehrung dieser Bedingung kann man für natürliche Zahlen testen, ob sie zusammengesetzt sind. Ist nämlich an−1−1 für eine zu n teilerfremde Basis a nicht durch n teilbar, so kann n nicht prim sein.Zum Beispiel kann man aus 29-1 = 28 = 256 = 28 ⋅ 9 + 4 ≡ 4 mod 9 schließen, dass die Zahl n = 9 zusammengesetzt ist.

Der fermatsche Primzahltest verläuft so:

  • Eingabe: n, die zu testende natürliche Zahl,
  • Ergebnis: zusammengesetzt oder keine Aussage
  • Wähle eine Basis a mit 1 < a < n aus. Prüfe, ob n und a teilerfremd sind.
    • Wenn sie nicht teilerfremd sind, dann ist das Ergebnis zusammengesetzt. Ansonsten:
    • Wenn an−1 ≢ 1 mod n, 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.

Diskussion