Diskussion:Fermatscher Primzahltest

Programm

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)

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)

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)

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 $2^{n-1}-1\mod n$ zutrifft. Das dem nicht so ist, hat AFAIK Euler nachgewiesen. --Arbol01 20:40, 28. Mai 2005 (CEST)

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)

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)

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)

Tabelle

Hast du auch ein Gegenbeispiel mit einer ungeraden Zahl? Eigentlich ist der Test ja nur für ungerade Zahlen sinnvoll. Deshalb ist es wohl irreführend, dass die Tabelle auch gerade n enthält, hab das gleich mal geändert. -- Infimum 16:14, 7. Okt. 2009 (CEST)

Abschnitt: Carmichael-Zahlen

Die Basen im zweiten Teil der Formeln sind falsch (2 statt 3 bzw 11). Welche Erleuchtung soll mir eigentlich die "quadrierte Darstellung" bringen? Gibts dazu eine Regel, die mir das potenzieren erspart oder halbiert es nur meinen Loop in der Potenzberechnung?

Pyromg 09:48, 12. Dez. 2008 (CET)

Übersicht Primzahltests allgemein

Daniel Bernstein gibt auf http://cr.yp.to/primetests.html einen Überblick über die Literatur zum Beweis der Primzahleigenschaft einer Primzahl. Darunter auch - Ivan B. Damgård, Gudmund Skovbjerg Frandsen: An Extended Quadratic Frobenius Primality Test with Average and Worst Case Error Estimates. Preprint 2003, http://www.brics.dk/RS/03/9/index.html --TeesJ 08:40, 4. Jan. 2010 (CET)

Test auf Teilerfremdheit

Der Test auf Teilerfremdheit von $a$ und $n$ ist im Grunde unnötig. Wenn diese einen gemeinsamen Teiler $g$ haben, ist $a^{n-1}\mod n$ ein Vielfaches von $g$ und der Test sagt richtigerweise zusammengesetzt. Nur aus Effizienzgründen kann es sinnvoll sein, die Teilerfremdheit zu prüfen. Zumindest für kleine $a$ und große $n$ geht dies viel schneller als das Potenzieren $a^{n-1}$. --Megatherium (Diskussion) 13:16, 10. Okt. 2015 (CEST)