Fermatscher Primzahltest

Fermatscher Primzahltest

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

Inhaltsverzeichnis

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:

a^{p-1}\equiv 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 28 = 256 = 28·9 + 4 ≡ 4 mod 9 schließen, dass die Zahl 9 zusammengesetzt ist.

Der fermatsche Primzahltest verläuft so:

  • Eingabe: n: 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 a^{n-1}\not\equiv 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.

Fermatsche Pseudoprimzahlen

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

Verwendet man den fermatschen Primzahltest mit der Basis a = 2, 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.

n 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
2n − 1mod n 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 n = 340 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 2340 − 1, aber aufgrund 341=11·31 nicht prim.

Bis n = 2000 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 a gilt, dass die Anzahl der fermatschen Pseudoprimzahlen kleiner als x geteilt durch die Anzahl der Primzahlen kleiner als x mit wachsendem x gegen Null konvergiert).

Deterministische Verwendung und Alternativen

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 Primzahltests

Literatur


Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Fermatscher Primzahltest (Programm-Code) — ist ein aus Fermatscher Primzahltest ausgelagerter Quellcode. Hier ein Programm dazu: C Quellcode für ein Programm, das nach dem kleinen Fermatschen Satz, Primzahlen, Pseudoprimzahlen und Carmichaelzahlen unterscheidet: /* Ein Programm, zur… …   Deutsch Wikipedia

  • Primzahltest — Ein Primzahltest ist ein mathematisches Verfahren, um festzustellen, ob eine gegebene Zahl eine Primzahl ist oder nicht. Inhaltsverzeichnis 1 Praktische Anwendung 2 Bekannte Primzahltest Verfahren 2.1 Probedivision …   Deutsch Wikipedia

  • Fermat'scher Primzahltest — Mit dem fermatschen Primzahltest kann man Primzahlen von zusammengesetzten Zahlen unterscheiden. Der Test erhält eine Zahl n und eine Basis a als Eingabe. n muss eine ungerade Zahl > 3 sein. Außerdem muss a die Bedingung 1 < a < n − 1… …   Deutsch Wikipedia

  • PRIMES — Als Primzahltest bezeichnet man ein mathematisches Verfahren, mit dem ermittelt wird, ob eine gegebene Zahl eine Primzahl ist oder nicht. Inhaltsverzeichnis 1 Praktische Anwendung 2 Bekannte Primzahltest Verfahren 2.1 Probedivision 2.2 Sieb des… …   Deutsch Wikipedia

  • Primzahlentest — Als Primzahltest bezeichnet man ein mathematisches Verfahren, mit dem ermittelt wird, ob eine gegebene Zahl eine Primzahl ist oder nicht. Inhaltsverzeichnis 1 Praktische Anwendung 2 Bekannte Primzahltest Verfahren 2.1 Probedivision 2.2 Sieb des… …   Deutsch Wikipedia

  • Primzahl — Die Zahl 12 ist keine Primzahl. Eine Primzahl ist eine natürliche Zahl, die größer als eins und ausschließlich durch sich selbst und durch eins teilbar ist. Eine Primzahl ist also eine natürliche Zahl mit genau zwei natürlichen Zahlen als Teiler …   Deutsch Wikipedia

  • Fermat — Pierre de Fermat Pierre de Fermat [pjɛːʀ dəfɛʀˈma] (* vermutlich Ende 1607 oder Anfang 1608 in Beaumont de Lomagne; † 12. Januar 1665 in Castres) war ein französischer Mathematiker und Jurist …   Deutsch Wikipedia

  • Pierre De Fermat — [pjɛːʀ dəfɛʀˈma] (* vermutlich Ende 1607 oder Anfang 1608 in Beaumont de Lomagne; † 12. Januar 1665 in Castres) war ein französischer Mathematiker und Jurist …   Deutsch Wikipedia

  • Lucas-Test (Mathematik) — Der Lucas Test ist eine Weiterentwicklung des Fermatschen Primzahltests durch den Mathematiker Édouard Lucas. Der Test wurde in den 50er Jahren von Derrick Lehmer und später nochmals von John Brillhart und John L. Selfridge verbessert. Er sollte… …   Deutsch Wikipedia

  • Allan J.C. Cunningham — Allan Joseph Champneys Cunningham (* 1842 in Delhi; † 1928 in London) war ein britischer Mathematiker. Er begann seine militärische Karriere bei den bengalischen Ingenieuren der Ostindienkompanie. Von 1871 bis 1881 war Cunningham Mathematiklehrer …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”