Fermatscher Primzahltest

Mit dem Fermatschen Primzahltest - entwickelt von dem "Freizeitmathematiker" Pierre de Fermat - kann man aussagen ob eine mit hoher Wahrscheinlichkeit eine Primzahl ist. Daher wird dieses auch PRP-Test (= pr obable p rime) genannt.

Inhaltsverzeichnis

1 Anwendung des Kleinen Fermatschen Satzes 2 Pseudoprimzahlen 2.1 Carmichael-Zahlen 3 Was kann man tun wenn man sichere Ergebnisse bekommen will 4 Der Weg zum propabilistischen Primzahltest 5 Verbesserungen des Fermatschen Primzahltests 6 Literatur

Anwendung des Kleinen Fermatschen Satzes

Direkt aus dem Kleinen Fermatschen Satz folgt:

Ist p eine Primzahl dann ist n ^p-1 -1 durch p teilbar für alle Zahlen n < p.

Dies kann man mit Hilfe der Modulo -Funktion schreiben als:

Für alle Primzahlen p gilt (n ^p-1 -1)mod p = 0 mit n p.

oder auch:

Für alle Primzahlen p gilt (n ^p-1 )mod p = 1 mit n <

Beispiel: p = 5 ist eine

 n=1: 1 5-1  -1 = 0 ist teilbar durch n=2: 2 5-1  -1 = 15 ist teilbar durch n=3: 3 5-1  -1 = 80 ist teilbar durch n=4: 4 5-1  -1 = 255 ist teilbar durch  

Gegenbeispiel: p = 55 ist keine Primzahl denn für n = 2

 2 55-1 mod 55 = 2 54 mod 55 = ((2 27 mod 55) 2 )mod 55 = 49 ungleich 1 d.h. = 55 ist keine Primzahl.  

Würde für alle natürlichen Zahlen q mit q > 2 gelten das

 <math>n^{q-1} \mod q = 1</math> zutrifft q eine Primzahl ist dann hätte man prima Verfahren zum Testen auf Primzahlen.  

Pseudoprimzahlen

Es gibt Zahlen q die keine sind und für die dennoch gilt:

n ^q-1 -1 durch q teilbar für bestimmte Zahlen n < q bei denen n Teiler von q ist.

Beispiel: q = 21 ist eine da für n = 13 gilt

 13 21-1 mod 21 = 13 20 mod 21 = ((13 10 mod 21) 2 )mod 21 = 1  

Carmichael-Zahlen

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

 <math>n^{q-1} \mod q = 1</math> (für n teilerfremd zu q)  

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

 Basis 3: 3 560 mod 561 = ((2 280 mod 561) 2 )mod 561 = 375  

 Basis 11: 11 560 mod 561 = ((2 280 mod 561) 2 )mod 55 = 154  

 Auch für die Basen 17 33 und 187 die alle Teiler von 561 gilt das die Zahl 561 keine Primzahl Für alle anderen Basen die keine Teiler 561 sind gilt: n 560 mod 561 = ((a 280 mod 561) 2 )mod 561 = 1  

Was kann man tun wenn man sichere Ergebnisse bekommen will

Wenn man nur auf die Basis testet dann kann man nur bis 340 sein das man zu 100% ein korrektes kommt. Wenn man parallel auf mehrere Basen Beispiel 2 3 und 5) testet erhöht die sichere Grenze nach oben:

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

Hier ein Programm dazu: C-Quellcode für Programm das nach dem kleinen Fermatschen Satz Pseudoprimzahlen und Carmichaelzahlen unterscheidet:

 /* Ein Programm zur Ermittlung von Pseudoprimzahlen */ /* und Charmichaelzahlen (starke Pseudoprimzahlen) /* Ein extrem langsames Progeamm */ #include int primfeld[400000]; int tst[400000]; unsigned long modup(unsigned x unsigned long y) { unsigned long xtemp = 1; for(mindex=1;mindex<=(y-1);mindex++) { xtemp *= xtemp %=y; } return(xtemp); } void main() unsigned long index index2 anzp=1 m dtm; tm1 tm2 tm3 gtm; FILE *prim; FILE FILE *cnbr; prim = fopen("prim.dat" "w"); pspr fopen("pspr.dat" "w"); cnbr = fopen("cnbr.dat" "w"); primfeld[1] 2; for(index=3;index<=4000000;index++) { tm1 = 0; tm2 0; tm3 = 0; /* faktor$ = */ for(index2=1;index2<=anzp;index2++) { m = modup(primfeld[index2] index); = m; if (m == 1) { = 1; tm3++; } if ( m 1) { tm2 = 2; } } = tm1 + tm2; if (gtm == { anzp++; primfeld[anzp] = index; fprintf(prim "%d index); } if (gtm == 3) { if (tm3 < dtm) { fprintf(pspr "%d: index); for(index2=1;index2<=anzp;index2++) { m = modup(primfeld[index2] index); (m == 1) { fprintf(pspr "%d " } } fprintf(pspr "\n" 0); } if >= dtm) { fprintf(pspr "%d: " index); { m = modup(primfeld[index2] index); if (m 1) { fprintf(cnbr "N%d " primfeld[index2]); } fprintf(cnbr "\n" 0); } } } fclose(prim); fclose(cnbr); }  

Obwohl das Programm zu 100% korrekte zurückliefert ist es weniger als Primzahltest sondern als Sieb für Pseudoprimzahlen und Carmichaelzahlen geeignet.

Der Weg zum propabilistischen Primzahltest

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

Dabei gibt es zwei Aspekte:

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

Der andere Aspekt ist die Prüfung der Breite. Bezugen auf die 68 mögichen liefern 21 Primbasen für die 341 fälschlich Ergebnis "Primzahl" zurück. Das ist ein bisschen als 1/3. Im Fall der Carmichael-Zahl 561 99 von 102 Primzahlbasen. Bei größeren Carmichaelzahlen oft aus nicht viel mehr Primfaktoren zusammengesetz wird das Missverhältnis noch extremer. Darum vermeiden propabilistische Primzahltests das Problem der Carmichael-Zahlen.

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

Verbesserungen des Fermatschen Primzahltests

Gary Miller und Michael O.Rabin verbesserten Fermattest im so genannten Rabin-Miller-Test . Nicht-Primzahlen erkennt er mit doppelter Wahrscheinlichkeit.

Im Jahre 1980 stellten die Mathematiker Leonard M. Adleman R.S. R umely H. C ohen und H.W. L enstra Jr den nach ihnen benannten ARCL-Test vor. Dieser ist eine Weiterentwicklung des Primzahltests indem er Carmichael-Zahlen erkennt.

Literatur

• C.Pomerance J.L.Selfridge S.S.Wagstaff Jr. "The pseudoprimes to · 109 " Math. Comp. 35:151 (1980)
• Paolo Ribenboim The new Book of Prime Records (1996) Springer Verlag

Bücher zum Thema Fermatscher Primzahltest

Dieser Artikel von Wikipedia unterliegt der GNU FDL.