Fermatscher Primzahltest (Programm-Code)

Fermatscher Primzahltest (Programm-Code) ist ein aus Fermatscher Primzahltest ausgelagerter Quellcode.

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

 /* Ein Programm, zur Ermittlung von Primzahlen, Pseudoprimzahlen */
 /* und Charmichaelzahlen (starke Pseudoprimzahlen) */
 /* Ein extrem langsames Programm */
 
 #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(cnbr,"N%d, ",primfeld[index2]);
           }
         }
         fprintf(cnbr,"\n",0);
       }
     }
   }
   fclose(prim);
   fclose(pspr);
   fclose(cnbr);
 }

Erläuterungen zum Programm

Da das Programm nicht nur eine Zahl auf ihre Primalität prüft, sondern alle Zahlen von 3 bis Obergrenze abtestet, wird ein Array namens Primfeld bereitgehalten, in dem alle Primzahlen, die so nach und nach gefunden werden, abgelegt werden. Die 2 wird als Primzahl vorgegeben.

Getestet werden die Primzahlkandidaten nur durch die Primzahlen in dem Array.

Die Variablen tm1, tm2, tm3, gtm sind Prüfvariablen:

tm1 = 1 wenn für ein $a^{n-1} \mod a = 1$ gilt.

tm2 = 1 wenn für ein $a^{n-1} \mod a <> 1$ gilt.

tm3 wird jedes Mal um 1 erhöht, wenn die Bedingung für tm1 erfüllt wird.

gtm = tm1 + tm2, woraus folgt:

Wenn gtm = 1 ist, dann ist die zu prüfende Zahl n eine Primzahl

Wenn gtm = 2 ist, dann ist die zu prüfende Zahl n eine ganz gewöhnliche Zahl

Wenn gtm = 3 ist, dann ist die zu prüfende Zahl n eine Pseudoprimzahl

Wenn gtm = 3 ist, und es gilt, dass die Anzahl der gefundenen Pseudoprimbasen größer oder gleich der Hälfte der testenden Primzahlen ist, dann ist die zu prüfende Zahl n eine Carmichael-Zahl.

Obwohl das Programm zu 100% korrekte Primzahlen zurückliefert, ist es weniger als Primzahltest, sondern vielmehr als Sieb für Pseudoprimzahlen und Carmichael-Zahlen geeignet.