imported>Bildungskind: /* Fermatscher Primzahltest */ Wichtiges Wort, was erwähnt werden sollte

2024-07-25T15:06:41Z

Fermatscher Primzahltest: Wichtiges Wort, was erwähnt werden sollte

Neue Seite

Der '''fermatsche Primzahltest''' ist ein [[Primzahltest]], der auf dem [[Kleiner Fermatscher Satz|kleinen fermatschen Satz]] beruht. Er dient dazu, [[Primzahl]]en von [[Zusammengesetzte Zahl|zusammengesetzten Zahlen]] zu unterscheiden.

== Fermatscher Primzahltest ==
Der fermatsche Primzahltest beruht auf dem kleinen fermatschen Satz:<br />
Für jede Primzahl <math>p</math> und jede dazu [[Teilerfremdheit|teilerfremde]] natürliche Zahl <math>a</math> ist folgende [[Kongruenz (Zahlentheorie)|Kongruenz]] erfüllt:
: <math>a^{p-1}\equiv 1 \mod p</math> .

Durch Umkehrung dieser Bedingung kann man für natürliche Zahlen testen, ob sie zusammengesetzt sind. Ist nämlich <math>a^{n-1} - 1</math> für eine zu <math>n</math> teilerfremde Basis <math>a</math> nicht durch <math>n</math> teilbar, so kann <math>n</math> nicht prim sein. Zum Beispiel kann man aus <math>2^{9-1} =2^8 = 256 = 28\cdot 9 + 4 \equiv 4 \mod 9</math> schließen, dass die Zahl <math>n=9</math> zusammengesetzt ist.

Der fermatsche Primzahltest verläuft so:
* Eingabe: <math>n</math>, die zu testende natürliche Zahl, Ergebnis: ''zusammengesetzt'' oder ''keine Aussage''
* Wähle eine Basis <math>a</math> mit <math>1 < a < n</math> aus. Prüfe, ob <math>n</math> und <math>a</math> teilerfremd sind.
: Wenn sie nicht teilerfremd sind, dann ist das Ergebnis ''zusammengesetzt''. Ansonsten:
: Wenn <math>a^{n-1}\not\equiv 1 \mod n</math>, 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''. Zahlen, welche bestätigen, dass eine Zahl zusammengesetzt sind, nennt man auch ''Fermat-Zeugen''.

== Fermatsche Pseudoprimzahlen ==
Es gibt jedoch natürliche Zahlen <math>n</math>, die keine Primzahlen sind und für die dennoch für eine teilerfremde Basis <math>a</math> gilt, dass <math>a^{n-1} - 1</math> durch <math>n</math> teilbar ist. Solche Zahlen heißen [[fermatsche Pseudoprimzahl]]en zur Basis <math>a</math>. Besonders hartnäckige fermatsche Pseudoprimzahlen sind die [[Carmichael-Zahl]]en. Für diese ist <math>a^{n-1} - 1</math> für ''alle'' zu <math>n</math> teilerfremden Basen durch <math>n</math> teilbar.

Verwendet man den fermatschen Primzahltest mit der Basis <math>a=2</math>, 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.
{| class="wikitable"
|-
|class="hintergrundfarbe6" | '''<math>n</math>''' || 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
|-
|class="hintergrundfarbe6" | '''<math>2^{n-1}\bmod n</math>''' || 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 <math>n=340</math> 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 <math>2^{340}-1</math>, aber aufgrund <math>341 = 11 \cdot 31</math> nicht prim.

Bis <math>n=2000</math> gibt es 303 Primzahlen, aber nur 7 fermatsche Pseudoprimzahlen bezüglich 2, nämlich 341, 561, 645, 1105, 1387, 1729 und 1905 ({{OEIS|A001567}}). 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 <math>a</math> gilt, dass die Anzahl der fermatschen Pseudoprimzahlen kleiner als <math>x</math> geteilt durch die Anzahl der Primzahlen kleiner als <math>x</math> mit wachsendem <math>x</math> 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-Rabin-Test|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 Adleman|Leonard M. '''A'''dleman]], [[Carl Pomerance|Carl '''P'''omerance]], [[Robert Rumely|Robert '''R'''umely]], [[Henri Cohen (Mathematiker)|H. '''C'''ohen]] und [[Hendrik Lenstra|Hendrik W. '''L'''enstra Jr.]] den nach ihnen benannten ''APRCL-Test'' vor.

== Weitere Primzahltests ==
* [[Lucas-Test (Mathematik)|Lucas-Test]]
* [[Solovay-Strassen-Test]]
* [[Miller-Rabin-Test]]

== Literatur ==
* [[Paulo Ribenboim]]: ''Die Welt der Primzahlen''. Springer Verlag, 1996

[[Kategorie:Primzahl]]
[[Kategorie:Pierre de Fermat]]

Fermatscher Primzahltest - Versionsgeschichte

imported>Bildungskind: /* Fermatscher Primzahltest */ Wichtiges Wort, was erwähnt werden sollte