Diskussion:Fermatscher Primzahltest
aus Wikipedia, der freien Enzyklopädie
Das ich mit dem augenblicklichen Stand des Beitrags mit Pseudoprimzahlen und Charmichael-Zahlen nicht zufrieden bin, brauche ich nicht zu betonen (das sieht man an meinen Änderungsversuchen).
Das wichtigste: Charmichaelzahlen sind nicht die perfekten Pseudoprimzahlen. Die Basen, die Teiler der Charmichaelzahl sind, sind nicht blind für diese Charmichaelzahl.
Anbei eine Liste von psP und Charmichael-Zahlen, die ein von mir geschriebenes Programm gefiltert hat:
15: 11; 21: 13; 25: 7; 33: 23; 35: 29; 45: 17, 19, 37; 49: 19, 31; 52: 29; 57: 37; 65: 31, 47, 53; 66: 31, 37, 69: 47; 70: 11, 77: 43; 85: 13, 47, 67; 87: 59; 91: 3, 17, 23, 29, 43, 53, 61, 79; 93: 61; 99: 89; 105: 13, 29, 41, 43, 71, 83, 97; 111: 73; 117: 53, 73, 109; 121: 3; 123: 83; 124: 5; 130: 61; 133: 11, 31, 37, 83, 103, 107, 113; 135: 109; 143: 131; 145: 17, 41, 59; 147: 97; 148: 137; 153: 19, 53, 89, 127; 154: 23, 67; 155: 61; 159: 107; 161: 139; 165: 23, 43, 67, 89, 109, 131; 169: 19, 23, 89; 171: 37; 175: 101, 149, 151; 176: 97, 113; 185: 31, 43, 73, 149, 179; 186: 97, 109, 157, 163; 187: 67; 190: 11, 61, 101, 131; 195: 79, 131, 181; 205: 73, 83, 163, 173; 208: 113; 217: 5, 37, 61, 67, 149, 181, 191, 211; 221: 47, 103, 157; 225: 107, 199; 231: 13, 29, 41, 43, 71, 83, 97, 113, 127, 139, 167, 181, 197, 211, 223; 237: 157; 238: 137; 244: 13; 245: 97, 197; 246: 37, 139, 223; 247: 103, 107, 113, 179, 191; 249: 167; 255: 101, 239; 259: 11, 47, 73, 101, 137, 149, 211, 223, 233; 261: 17, 233; 265: 23, 83, 107, 211; 267: 179; 268: 29, 37; 273: 83, 181, 239; 275: 199; 276: 13, 73, 193; 285: 37, 113, 151, 191, 227, 229; 286: 3, 53, 113, 157, 191, 269; 287: 83; 289: 131, 179, 251; 291: 193; 292: 137; 297: 109; 301: 37, 79, 173, 179, 251, 257; 305: 11, 233; 310: 191, 211; 315: 71, 181, 251; 316: 181; 322: 277; 325: 7, 43, 101, 107, 149, 151, 157, 193, 199, 251, 257, 293, 307; 329: 281; 333: 73, 179; 335: 269; 339: 227; 341: 2, 23, 29, 47, 61, 89, 97, 101, 109, 139, 151, 157, 163, 233, 263, 271, 277, 281, 283, 311, 337; 343: 19; 344: 41, 97, 193; 345: 47, 137, 139, 229, 277; 351: 53; 357: 13, 239, 251, 293, 307; 361: 127, 293, 307; 363: 241; 364: 29, 53, 113; 365: 173, 293; 366: 241; 369: 73, 109, 163; 370: 71, 181, 211, 271; 371: 211; 375: 251; 377: 157, 233, 307; 385: 23, 43, 67, 89, 109, 131, 197, 199, 241, 263, 307, 331, 353, 373; 388: 61, 229; 391: 137; 393: 263; 396: 37, 181; 399: 113, 379; 403: 61, 181, 191, 211, 311, 347, 367, 373; 405: 163; 406: 233; 412: 149; 415: 331; 417: 277; 418: 353; 425: 43, 101, 149, 151, 157, 251, 257, 293, 307, 349; 426: 199, 409; 427: 13, 47, 109, 197, 257, 353, 367, 379; 429: 109, 131, 307; 430: 251; 435: 59, 71, 109, 139, 149, 151, 179, 181, 199, 239, 241, 281, 349, 401, 419, 431; 436: 281; 437: 229; 441: 197; 445: 179, 233; 448: 193; 451: 23, 31, 37, 59, 83, 107, 113, 127, 139, 163, 223, 269, 271, 277, 283, 353, 359, 373, 379, 409, 433; 455: 181; 459: 271; 465: 61, 311, 373, 433; 469: 29, 37, 97, 163, 239, 269, 373, 401, 431, 439; 471: 313; 475: 151, 349, 449; 477: 107; 481: 11, 23, 29, 31, 43, 47, 73, 97, 101, 103, 137, 149, 179, 191, 193, 199, 211, 223, 233, 251, 269, 307, 347, 359, 397, 401, 421, 433, 443, 467; 483: 139, 461; 485: 193, 269, 313, 389, 463; 493: 157, 191, 307, 463; 495: 89, 109, 199; 496: 97, 113, 193, 257; 505: 293, 313,; 506: 47; 507: 337; 511: 137, 211, 227, 283, 293, 373, 439, 503; 513: 379; 519: 347; 525: 43, 251, 293, 307, 349, 449; 527: 373; 529: 263, 359, 487; 532: 137, 149, 197, 233, 277, 389, 457; 533: 73, 83, 337; 537: 359; 539: 197; 545: 251; 549: 233, 487; 553: 23, 103, 157, 181, 293, 317, 419; 555: 149; 556: 181; 559: 79, 173, 179, 251, 257, 337, 467, 523; 561: N3, N11, N17, (Charmichaelzahl)
Weiter möchte ich aus Rücksicht nicht machen.
--Arbol01 3. März 2004
Hier noch das nicht ganz konforme C-Listing:
/* Ein Programm, zur Ermittlung von Primzahlen, Pseudoprimzahlen */
/* und Charmichaelzahlen (starke Pseudoprimzahlen) */
/* Ein extrem langsames Progeamm */
#include <stdio.h>
int primfeld[400000];
int tst[400000];
unsigned long modup(unsigned long x, unsigned long y)
{
unsigned long mindex, xtemp = 1;
for(mindex=1;mindex<=(y-1);mindex++)
{
xtemp *= x;
xtemp %=y;
}
return(xtemp);
}
void main()
{
unsigned long index, index2, anzp=1, m, dtm;
int tm1, tm2, tm3, gtm;
FILE *prim;
FILE *pspr;
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);
tst[index2] = m;
if (m == 1)
{
tm1 = 1;
tm3++;
}
if ( m != 1) { tm2 = 2; }
}
gtm = tm1 + tm2;
if (gtm == 1)
{
anzp++;
primfeld[anzp] = index;
fprintf(prim,"%d \n",index);
}
if (gtm == 3)
{
dtm=anzp/2;
if (tm3 < dtm)
{
fprintf(pspr,"%d: ",index);
for(index2=1;index2<=anzp;index2++)
{
m = modup(primfeld[index2], index);
if (m == 1)
{
fprintf(pspr,"%d, ",primfeld[index2]);
}
}
fprintf(pspr,"\n",0);
}
if (tm3 >= dtm)
{
fprintf(pspr,"%d: ",index);
for(index2=1;index2<=anzp;index2++)
{
m = modup(primfeld[index2], index);
if (m != 1)
{
fprintf(pspr,"N%d, ",primfeld[index2]);
}
}
fprintf(cnbr,"\n",0);
}
}
}
fclose(prim);
fclose(pspr);
fclose(cnbr);
}
--Arbol01 17:15, 3. März 2004
- Es ist eine schlechte Idee, Carmichaelzahlen als "starke Pseudoprimzahlen" zu bezeichnen. Denn es gibt schon den Begriff "strong probable (pseudo)prime bezüglich a" und dieser wird gebraucht für die (zusammengesetzten) Zahlen, die den strong probable prime test, auch Miller-Rabin-Test genannt, bezüglich der Basis a bestehen. Das ist etwas Anderes als Carmichaelzahlen.
141.24.48.70 11:52, 27. Mai 2005 (CEST)
Inhaltsverzeichnis |
[Bearbeiten] TeX-Syntax
Wäre super, wenn die Formeln und Variablenamen im Artikel mal bei Gelegenheit jemand in die Wikipedia:TeX-Syntax konvertieren könnte. Stern 03:03, 31. Mai 2004 (CEST)
- Ist hiermit geschehen. --Arbol01 11:37, 31. Mai 2004 (CEST)
[Bearbeiten] 100%-iger Test
Gibt's eine Formel / obere Abschätzung, bis zu welcher Primzahl man testen muss, um sicherzustellen, dass n eine Primzahl ist (und die natürlich kleiner als die Quadratwurzel von n ist ;-))?
- Wenn n unbegrenzt groß sein kann, dann muß man immer wenigstens bis zur Quadratwurzel testen. Wenn man mit Hilfe des kleinen Fermat testen will, dann muß man AFAIK alle Primzahlen < n testen, wenn man sicher sein will, aber da kann ich mich natürlich auch irren. --Arbol01 22:53, 11. Feb 2005 (CET)
Nachtrag: Egal welches Verfahren man nun nimmt, man muß bis Wurzel aus n testen, um 100%ig sicher sein zu können. --Arbol01 22:58, 11. Feb 2005 (CET)
- Beim Durchprobieren muss man stets bis zur Wurzel (abgerundet) testen, sonst werden z.B. aus einem Primzahlzwillingspaar zusammengesetzte Zahlen nicht als solche erkannt. Das Durchprobieren benötigt aber exponentielle Laufzeit (in der Länge der Primzahl) und ist damit nicht sonderlich effizient. Seit 2002 kennt man den AKS-Primzahltest, das ist ein nicht-probabilistischer, in Polynomialzeit arbeitender Primzahltest. Für hinreichend große Primzahlen arbeitet dieser Test wesentlich schneller als das Durchprobieren.--MKI 12:11, 27. Mai 2005 (CEST)
Carmichael-Zahlen haben wenigstens 3 Primteiler, damit hat man Carmichael-Zahlen bereits nach der dritten Wurzel. Und bei Pseudoprimzahlen, bei denen es zwar möglich ist, daß sie nur zwei Primteiler haben, ist es völlig ausreichend zur dritten Wurzel zu gehen, da
WSA: für alle a aus {1..n^(1/3)} ist a^(n-1) = 1 mod n, allerdings gibt es a aus {n^(1/3)..n} mit ggT(a,n)=1 und a^(n-1) = 1 mod n:
Sei a aus {n^(1/3)..n} mit ggT(a,n)=1 und a^(n-1) = 1 mod n, m:=[n^(1/4)], m^(n-1)=1 mod n. Dann ist M={a*m, a*m^2, a*m^3} geschnitten {1..n^(1/3)} nichtleer, z aus M mit z^(n-1)!=1 mod n
qed
Was aber nicht heißt, daß man das verwenden sollte, da es sehr langsam ist --82.135.5.250 17:38, 24. Jun 2005 (CEST)
[Bearbeiten] Geht der _Test_ wirklich auf Fermat zurück?
Seid ihr euch ganz sicher, dass Fermat nicht nur den Kleinen Fermatschen Satz kannte, sondern tatsächlich auch den Fermatschen Primzahltest entwickelt hat?
141.24.48.70 18:41, 27. Mai 2005 (CEST)
- Der kleine fermatsche Satz geht direkt auf Pierre de Fermat zurück. Von Primzahltest war damals noch nicht die Rede. Allerdings vermutete de Fermat, das die Umkehrung auf alle Primzahlen zutrifft, daß also n prim ist, wenn
zutrifft. Das dem nicht so ist, hat AFAIK Euler nachgewiesen. --Arbol01 20:40, 28. Mai 2005 (CEST)
[Bearbeiten] Abschnitt "Anwendung des Kleinen Fermatschen Satzes"
Ich finde, mehrere äquivalente Formulierungen des Kleinen Fermatschen Satzes gehören auf die Seite des Kleinen Fermatschen Satzes und nicht des Primzahltests. Hier sollte nur eine Formulierung stehen und zwar so eine, mit der man sofort sieht, was der Satz mit dem Test zu tun hat.
Ebenso finde ich es nicht sinnvoll vorzurechnen, dass Primzahlen die Aussage des Kleinen Fermatschen Satzes erfüllen. Ist doch klar, dass da immer 1 rauskommt, so ist das nun mal bei mathematischen Sätzen, sie gelten immer. Viel interessanter ist es da doch zu sehen, dass für zusammengesetzte Zahlen die Aussage des Kleinen Fermatschen Satzes fast immer verletzt ist. Das ist nicht selbstverständlich und das macht den Kleinen Fermatschen Satz überhaupt erst tauglich als Primzahltest. -- Infimum 19:50, 3. Jun 2005 (CEST)
- Naja, was die Tauglichkeit betrifft, ist der kleine Fermat reichlich ungeeignet als Primzahltest. Da gibt es nun wirklich geeignetere. An und für sich finde ich den ganzen Artikel eher überflüssig. --Arbol01 00:55, 14. Jun 2005 (CEST)
-
- Ich finde, diesen Test extrem sinnvoll - er ist leicht zu verstehen und macht einem das konzept einer pseudozufallszahl klar. Für die Praxis ist er natürlich absolut ungeeignet.--82.135.5.250 17:49, 24. Jun 2005 (CEST)
-
-
- Auch in der Praxis wird der Test eingesetzt, z.B. von der GMP-Bibliothek: Wenn man mit mpz_probab_prime_p() prüfen will, ob man eine Primzahl vor sich hat, wird vor dem Miller-Rabin-Test einmal der Fermat-Test mit einer festen Basis aufgerufen. Das ist bestimmt kein Versehen. Infimum 18:10, 22. Mär 2006 (CET)
-
[Bearbeiten] Sichere Grenze für Basen 2 und 3 unter 2700
"Bei 2 und 3 liegt die sichere Grenze bei 2700" - Das stimmt nicht. Ein Gegenbeispiel ist 1105, offensichtlich keine Primzahl, kleiner als 2700 und doch ist 2^1104 mod 1105 = 3^1104 mod 1105 = 1. Ich nehme die Aussage mal aus dem Artikel. Wie lautet denn die korrekte Grenze?
- 1104. Anscheinend hatte ich die Carmichael-Zahl 1105 übersehen, wein sie in meiner Pseudoprimzahl-Liste mit 1105: N5, N13, N17 steht. --Arbol01 16:52, 2. Nov 2005 (CET)
[Bearbeiten] Fast schon ein Widerspruch (im Text)
1. Abschnitt „Fermatscher Primzahltest“: … Außerdem muss a die Bedingung 1 < a < n − 1 erfüllen. …
2. Abschnitt „Wie der Fermatsche Test arbeitet“: … Jedoch sollte man beachten, dass die Basis a - selbst wenn diese prim ist - vom Test nicht als Primzahl erkannt wird …
Wie sollte der Test denn auf a angewendet werden? Immerhin würde a dabei zu n „mutieren“ und könnte wg. der Bedingung aus 1. kaum mit/gegen sich selbst getestet werden.
--84.151.214.213
- Ich finde, dass der Satz "Jedoch sollte man beachten...." Verwirrung stiftet. Es ist wohl besser, ihn zu streichen und dafür im Artikel deutlich zu machen, dass n getestet werden soll und a nur ein Hilfsmittel dazu ist, von dem wir nicht wissen, ob es prim ist (und es auch gar nicht wissen müssen). --Infimum 13:46, 29. Sep 2006 (CEST)
