Hauptmenü öffnen

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

Inhaltsverzeichnis

Fermatscher PrimzahltestBearbeiten

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.

Fermatsche PseudoprimzahlenBearbeiten

Es gibt jedoch natürliche Zahlen  , die keine Primzahlen sind und für die dennoch für eine teilerfremde Basis   gilt, dass   durch   teilbar ist. Solche Zahlen heißen fermatsche Pseudoprimzahlen zur Basis  . Besonders hartnäckige fermatsche Pseudoprimzahlen sind die Carmichael-Zahlen. Für diese ist   für alle zu   teilerfremden Basen durch   teilbar.

Verwendet man den fermatschen Primzahltest mit der Basis  , so kann schon recht sicher festgestellt werden, ob eine Zahl eine Primzahl ist oder nicht. Die folgende Tabelle zeigt das Ergebnis der Berechnung für die Zahlen 3 bis 29.

  3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
  1 0 1 2 1 0 4 2 1 8 1 2 4 0 1 14 1 8 4 2 1 8 16 2 13 8 1

Diese Tabelle kann bis   fortgesetzt werden und immer steht unter jeder Primzahl eine 1 und unter jeder zusammengesetzten Zahl eine Zahl verschieden von 1. Die 341 ist nämlich die erste fermatsche Pseudoprimzahl bezüglich der Basis 2: 341 ist ein Teiler von  , aber aufgrund   nicht prim.

Bis   gibt es 303 Primzahlen, aber nur 7 fermatsche Pseudoprimzahlen bezüglich 2, nämlich 341, 561, 645, 1105, 1387, 1729 und 1905 (Folge A001567 in OEIS). Wählt man eine andere Basis, so kommt man zu ähnlichen Ergebnissen. Es wurde von Paul Erdős bewiesen, dass die Pseudoprimzahlen zu jeder Basis verschwindend wenige sind im Vergleich zu den Primzahlen (zu jeder Basis   gilt, dass die Anzahl der fermatschen Pseudoprimzahlen kleiner als   geteilt durch die Anzahl der Primzahlen kleiner als   mit wachsendem   gegen null konvergiert).

Deterministische Verwendung und AlternativenBearbeiten

Wenn man die Basis 2 verwendet, dann ist man also bis zur Zahl 340 sicher, ein korrektes Ergebnis zu bekommen. Testet man mit mehreren Basen (zum Beispiel 2, 3 und 5), so erhöht sich die sichere Grenze nach oben. Der Test mit den Basen 2 und 3 ist zum Beispiel bis 1104 korrekt; bei Verwendung der Basen 2, 3 und 5 erhöht sich die Grenze auf 1728.

In der Praxis werden andere Primzahltests bevorzugt, z. B. der Miller-Selfridge-Rabin-Test, da sie mit höherer Wahrscheinlichkeit den Fall ausschließen, dass eine zusammengesetzte Zahl nicht als solche erkannt wird.

Jedoch gab es auch Weiterentwicklungen des fermatschen Primzahltests: zum Beispiel stellten ab 1983 die Mathematiker Leonard M. Adleman, Carl Pomerance, Robert Rumely, H. Cohen und Hendrik W. Lenstra Jr. den nach ihnen benannten APRCL-Test vor.

Weitere PrimzahltestsBearbeiten

LiteraturBearbeiten