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 $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 $a^{n-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 $2^{9-1}=2^{8}=256=28\cdot 9+4\equiv 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 $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. Zahlen, welche bestätigen, dass eine Zahl zusammengesetzt sind, nennt man auch Fermat-Zeugen.

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 $a^{n-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 $a^{n-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
$2^{n-1}{\bmod {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 $2^{340}-1$, aber aufgrund $341=11\cdot 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

• Lucas-Test
• Solovay-Strassen-Test
• Miller-Rabin-Test

Literatur

• Paulo Ribenboim: Die Welt der Primzahlen. Springer Verlag, 1996