Fermatscher Primzahltest

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

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$ erfüllen. Der Test liefert eines von zwei möglichen Ergebnissen: entweder

" $n$ ist (bezüglich $a$ ) Primzahlkandidat (engl: probable prime)" oder
" $n$ ist keine Primzahl".

Im letzteren Fall ist $n$ keine Primzahl. Falls der Test $n$ zum Primzahlkandidaten erklärt, kann man in den meisten Fällen davon ausgehen, dass $n$ eine Primzahl ist. $n$ ist also "wahrscheinlich" eine Primzahl. Daher wird dieses Verfahren auch PRP-Test (= probable prime test) genannt.

Inhaltsverzeichnis

1 Wie der Fermatsche Test arbeitet
2 Korrektheit des Fermatschen Primzahltests
3 Wie man den Fermatschen Primzahltest benutzt
4 Carmichael-Zahlen
5 Was kann man tun, wenn man 100% sichere Ergebnisse bekommen will
6 Der Weg zum probabilistischen Primzahltest
- 6.1 Suche mit nur einer Basis, bei zufälliger Auswahl der zu testenden Zahl
- 6.2 Breitensuche mit zufälliger Auswahl einer oder mehrerer Basen (mit möglicher zufälliger Auswahl der zu testenden Zahl)
7 Verbesserungen des Fermatschen Primzahltests
8 Primzahltest nach Solovay-Strassen
9 Literatur

[Bearbeiten] Wie der Fermatsche Test arbeitet

Der Fermatsche Primzahltest besteht aus zwei Schritten:

Berechne $b = a^{n-1} \mod n$ .
Falls $b = 1$ , gib " $n$ ist (bezüglich $a$ ) Primzahlkandidat" aus, andernfalls " $n$ ist keine Primzahl".

Dabei bedeutet die Operation $a \mod n$ den Divisionsrest der ganzzahligen Division von $a$ durch $n$ (siehe auch Kongruenz in der Zahlentheorie). Jedoch sollte man beachten, dass die Basis $a$ - selbst wenn diese prim ist - vom Test nicht als Primzahl erkannt wird, da $n^m \equiv 0 \mod n$ für alle $n$ und $m$ gilt.

[Bearbeiten] Korrektheit des Fermatschen Primzahltests

Direkt aus dem Kleinen Fermatschen Satz folgt:

Wenn

p

eine Primzahl ist, dann gilt für jede Zahl

a

, die teilerfremd zu

p

ist: $a^{p-1} \equiv 1 \mod p$

Falls $n$ und $a$ die ursprünglichen Bedingungen erfüllt, dann ist $a$ nicht durch $n$ teilbar. Falls $n$ eine Primzahl ist, so ist aufgrund des Kleinen Fermatschen Satzes $b = 1$ . Ist $b$ nicht gleich $1$ , dann ist $n$ keine Primzahl, und der Test gibt " $n$ ist keine Primzahl" aus.

[Bearbeiten] Wie man den Fermatschen Primzahltest benutzt

Den Fermatschen Primzahltest setzt man ein, wenn man eine (große) Zahl $n$ gegeben hat, von der man herausfinden möchte, ob sie eine Primzahl ist oder nicht. In den meisten Fällen reicht es dann nämlich, den Fermatschen Primzahltest mit $a = 2$ zu starten, um die richtige Antwort zu finden:

n        3   4   5   6   7   8   9   10   11   12   13   14   15   16
2^(n-1)  1   0   1   2   1   0   4    2    1    8    1    2    4    0
(mod n)

n        17   18   19    20   21   22   23   24   25   26   27   28   29
2^(n-1)   1   14    1     8    4    2    1    8   16    2   13    8    1
(mod n)

Diese Tabelle könnte man noch bis über 300 fortsetzen und immer würde nicht nur unter jeder Primzahl eine 1 stehen (das muss sowieso der Fall sein, wegen des Kleinen Fermatschen Satzes), sondern und auch unter jeder zusammengesetzten Zahl eine Zahl verschieden von 1 -- das ist durch den Kleinen Fermatschen Satz nicht garantiert. Erst mit 341 ist das erste Mal ein Primzahlkandidat bezüglich 2 keine Primzahl, sondern eine zusammengesetzte Zahl, nämlich 341=11*31. Eine Zahl, die zwar ein Primzahlkandidat, aber keine Primzahl ist, wird Pseudoprimzahl genannt. Bis 2000 gibt es 303 Primzahlen, aber nur 7 Pseudoprimzahlen bezüglich 2, nämlich 341, 561, 645, 1105, 1387, 1729 und 1905.

Wählt man nicht $a = 2$ , sondern eine andere erlaubte Zahl, so kommt man zu ähnlichen Ergebnissen. Dies muss auch so sein, denn Paul Erdös hat bewiesen, dass die Pseudoprimzahlen zu einer festen Basis $a$ verschwindend wenige sind im Vergleich zu den Primzahlen.

[Bearbeiten] Carmichael-Zahlen

Besonders hartnäckige Pseudoprimzahlen sind die Carmichael-Zahlen, für die gilt, dass alle Basen n mit 1 < n < q, die nicht Teiler von q sind:

 (für alle n teilerfremd zu q)

Als Beispiel dafür die 561 (sie ist die kleinste Carmichael-Zahl):

Basis 3:

Basis 11:

Auch für die Basen 17, 33, 51 und 187, die alle Teiler von 561 sind, gilt, dass die Zahl 561 keine Primzahl ist. Für alle anderen Basen, die keine Teiler von 561 sind, gilt:

[Bearbeiten] Was kann man tun, wenn man 100% sichere Ergebnisse bekommen will

Wenn man nur auf die Basis 2 testet, dann kann man nur bis 340 sicher sein, dass man zu 100% ein korrektes Ergebnis bekommt. Wenn man parallel auf mehrere Basen (zum Beispiel 2, 3 und 5) testet, erhöht sich die sichere Grenze nach oben:

Bei einem Test zur Basis 2 und 3 ist 1105 die erste Pseudoprimzahl, bei 2, 3 und 5 ist 1729 erste Pseudoprimzahl, bei 2, 3, 5, 7 und 11 liegt die sichere Grenze bei 29340 und bei 2, 3, 5, 7, 11 und 13 liegt sie bei 162401. Leider macht jede weitere Basis ein Programm langsamer. Wenn man konsequent auf alle Basen testet, bekommt man zwar ein Programm, das zu 100% sichere Primzahlen zurückliefert, aber viel langsamer als ein Programm ist, das eine Zahl konsequent auf alle möglichen Teiler testet.

Quellcode

[Bearbeiten] Der Weg zum probabilistischen Primzahltest

Man kann nun versuchen, diesen Test zu vereinfachen und den Rechenaufwand deutlich zu reduzieren, wenn man eine etwas geringere Wahrscheinlichkeit in der Primzahlaussage in Kauf nimmt.

Dabei gibt es zwei Aspekte:

[Bearbeiten] Suche mit nur einer Basis, bei zufälliger Auswahl der zu testenden Zahl

Wenn man nur eine Basis nimmt, vorzugsweise die Basis 2, dann hat man eine relativ geringe Wahrscheinlichkeit, aber den Umstand, dass wenn man schon eine Pseudoprimzahl wie 341 trifft, dass diese zu 100% falsch ist, auch wenn die Wahrscheinlichkeit auf die 341 zu treffen nur gering ist. Jedesmal, wenn man auf 341 prüft, wird der kleine Fermatsche Satz in der Kombination mit 341 und Basis 2 das Urteil "Primzahl" zurückgeben.

[Bearbeiten] Breitensuche mit zufälliger Auswahl einer oder mehrerer Basen (mit möglicher zufälliger Auswahl der zu testenden Zahl)

Der andere Aspekt ist die Prüfung in der Breite. Bezogen auf die 68 möglichen Primzahlbasen liefern 21 Primbasen für die 341 falsch das Ergebnis "Primzahl" zurück. Das ist ein bisschen weniger als 1/3.

Hier würde eine Verwendung der Eulerschen Formel anstelle des kleinen Fermat zu einer Verringerung der Anzahl der ein falsches Ergebnis liefernden Primbasen führen. Wo beim kleinen Fermat zur Pseudoprimzahl 91 noch 8 Primbasen (3, 17, 23, 29, 43, 53, 61 und 79) falsch eine Primzahl melden, sind es bei der Eulerschen Formel noch die Hälfte (17, 29, 53 und 79). Das verbessert einen probabilistischen Ansatz erheblich.

Im Fall der Carmichael-Zahl 561 lügen 99 von 102 Primzahlbasen. Bei größeren Carmichaelzahlen, die oft aus nicht viel mehr Primfaktoren zusammengesetzt sind, wird das Missverhältnis noch extremer. Darum vermeiden bessere probabilistische Primzahltests das Problem der Carmichael-Zahlen.

Hier eine Tabelle von besonders guten Pseudoprimzahlen (die keine Carmichael-Zahlen sind). Die 15 ist aufgeführt, weil sie die erste Pseudoprimzahl ist, und die 91 ist in ihrer Umgebung eine relativ gute Pseudoprimzahl.

Pseudoprimzahl	A	B	C	Primfaktoren
15	6	1	83,33%	3 * 5
91	24	8	66,67%	7 * 13
703	126	56	55,56%	19 * 37
1891	290	139	52,07%	31 * 61
2701	393	191	51,4%	37 * 73
11305	1366	667	50,44%	5 * 7 * 17 * 19
12403	1480	739	50,07%	79 * 157
13981	1650	815	50,06%	11 * 31 * 41
18721	2137	1070	49,93%	97 * 193

A: Anzahl der Primzahlen zwischen 2 und der entsprechenden Pseudoprimzahl

B: Anzahl der Primzahlen aus A die falsch behaupten, die entsprechende Pseudoprimzahl sei eine Primzahl

C: Die Wahrscheinlichkeit, bei Auswahl einer Primzahlbasis eine der nicht lügenden zu erwischen

Bei den Carmichael-Zahlen geht die Wahrscheinlichkeit, eine der nichtlügenden Primzahlbasen zu erwischen gegen 0.

Wenn man zufällig mehrere Primzahlbasen auswählt, dann steigt die Wahrscheinlichkeit, Pseudoprimzahlen als solche zu entlarven:

Anzahl der testenden Primzahlbasen

	1	2	3	4	5
91	83,33%	89,86%	97,23%	99,34%	99,86%
561	2,94%	5,82%	8,65%	11,42%	14,13%
703	55,56%	80,44%	91,48%	96,33%	98,44%
1729	1,11%	2,22%	3,32%	4,41%	5,49%
1891	52,07%	77,11%	89,11%	94,85%	97,56%

Für die Praxis bedeutet das: Oft reicht der Nachweis aus, dass p pseudoprim ist zur Basis 2. Will man die Sicherheit weiter erhöhen, dann muss man eben weitere Zeugen finden, d.h. weitere Zahlen a, zu deren Basis p pseudoprim ist.
Im Grenzfall testet man alle Zahlen a < p, d.h. man führt den gesamten Fermattest durch.

[Bearbeiten] Verbesserungen des Fermatschen Primzahltests

1891 wurde der Fermatsche Primzahltest von Edouard Lucas als Lucas-Test verbessert.

1967 wurde dieser Lucas-Test nochmal von Brillhart und Selfridge verbessert.

[Bearbeiten] Primzahltest nach Solovay-Strassen

Der Solovay-Strassen-Test benutzt nicht den kleinen Fermatschen Satz: $a^{n-1} \equiv 1 \mod n$ , sondern den etwas strengeren Satz nach Euler: $a^{\frac{n-1}{2}} \equiv 1 \mod n$ bzw. $a^{\frac{n-1}{2}} \equiv (n-1) \mod n$ . Außerdem wird das Ergebnis noch mit dem Jacobi-Symbol J(a,n) abgeglichen.

[Bearbeiten] Literatur

Carl Pomerance, John L. Selfridge, Samuel S. Wagstaff Jr.: The pseudoprimes to 25 · 109, in: Mathematics and Computation, 35:151 (1980) 1003-1026.
Paolo Ribenboim: The new Book of Prime Number Records, Springer, New York, 1996, ISBN 0-387-94457-5

Von „http://de.wikipedia.org../../../f/e/r/Fermatscher_Primzahltest_ec2f.html“

Kategorie: Zahlentheorie