Fermatscher Primzahltest (Programm-Code): Unterschied zwischen den Versionen

← Zum vorherigen Versionsunterschied Zum nächsten Versionsunterschied →

Version vom 13. Dezember 2009, 14:06 Uhr

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:

/* REXX-Programm */
say 'Only a Library!'
exit 1
/* */
/* */
m_u: procedure
  arg a,l,m
/* initialisierung */
  as = a
  ai = a
  li = (l-1)
  DO li
    a = a * ai
    a = a // m
  END
return a

mod_up.r

A sourcecode to calculate fermat pseudoprimes

/* Ein REXX-Programm */

call load 'mod_up.r'
anzfpspr=0
do i = 2 to 99999
  fpsprb.i = " "
  t=0
  t2=0
  do i2 = 2 to (i-2)
    call m_u i2, (i-1), i
    pt = result
    if (pt = 1) then do
                        t = 1
                        fpsprb.i2 = fpsprb.i2||i||", "
    end
    if (pt > 1) then t2 = 1
  end
  tg = t + t2
  if (tg = 2) then do
                     anzfpspr = anzfpspr + 1
                     ausgabe = "fpspr."||anzfpspr||" = "||i
                     say ausgabe
                     lineout("epspr_var.txt",ausgabe)
  end
end
lineout("fpsprb_table2.txt","{| {{prettytable}")
do i = 2 to 99999
  ausgabe = "|"||i||" ||"||fpsprb.i||"@"
  say ausgabe
  lineout("fpsprb_table2.txt",ausgabe)
  lineout("fpsprb_table2.txt","|-")
end

The File "epspr_var.txt" is used to calculate euler pseudoprimes. The file "fpsprb_table2.txt" is a table in Wikimedia format.

The List:

fpspr.1 = 15 
fpspr.2 = 21 
fpspr.3 = 25 
fpspr.4 = 28 
fpspr.5 = 33 
fpspr.6 = 35 
fpspr.7 = 39 
fpspr.8 = 45 
fpspr.9 = 49
.
.
.
fpspr.5974 = 11620 
fpspr.5975 = 11623 
fpspr.5976 = 11625 
fpspr.5977 = 11627 
fpspr.5978 = 11629

will be generate as "epspr_var.txt" by the following Souerce code to calculate the fermat pseudoprimes:

/* Ein REXX-Programm */
call load 'mod_up.r'
anzfpspr=0
do i = 2 to 99999
  fpsprb.i = " "
  t=0
  t2=0
  do i2 = 2 to (i-2)
    call m_u i2, (i-1), i
    pt = result
    if (pt = 1) then do
                        t = 1
                        fpsprb.i2 = fpsprb.i2||i||", "
    end
    if (pt > 1) then t2 = 1
  end
  tg = t + t2
  if (tg = 2) then do
                     anzfpspr = anzfpspr + 1
                     ausgabe = "fpspr."||anzfpspr||" = "||i
                     say ausgabe
                     lineout("epspr_var.txt",ausgabe)
  end
end
lineout("fpsprb_table2.txt","{| {{prettytable}")
do i = 2 to 99999
  ausgabe = "|"||i||" ||"||fpsprb.i||"@"
  say ausgabe
  lineout("fpsprb_table2.txt",ausgabe)
  lineout("fpsprb_table2.txt","|-")
end

@@ Zeile 1: / Zeile 1: @@
 '''Fermatscher Primzahltest (Programm-Code)''' ist ein aus [[Fermatscher Primzahltest]] ausgelagerter Quellcode.
@@ Zeile 5: / Zeile 4: @@
 Hier ein Programm dazu:
 C-Quellcode für ein Programm, das nach dem kleinen Fermatschen Satz, Primzahlen, Pseudoprimzahlen und Carmichaelzahlen unterscheidet:
-<source lang=cpp>
- /* 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);
- }
-</source>
-== 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.
+<code>
+ /* REXX-Programm */
+ say 'Only a Library!'
+ exit 1
+ /* */
+ /* */
+ m_u: procedure
+   arg a,l,m
+ /* initialisierung */
+   as = a
+   ai = a
+   li = (l-1)
+   DO li
+     a = a * ai
+     a = a // m
+   END
+ return a
+</code>
+:mod_up.r
-Die Variablen tm1, tm2, tm3, gtm sind Prüfvariablen:
+A sourcecode to calculate fermat pseudoprimes
-:tm1 = 1 wenn für ein <math>a^{n-1} \mod a = 1</math> gilt.
+<code>
-:tm2 = 1 wenn für ein <math>a^{n-1} \mod a <> 1</math> gilt.
+/* Ein REXX-Programm */
-:tm3 wird jedes Mal um 1 erhöht, wenn die Bedingung für tm1 erfüllt wird.
+ call load 'mod_up.r'
-:gtm = tm1 + tm2, woraus folgt:
+ anzfpspr=0
-::Wenn gtm = 1 ist, dann ist die zu prüfende Zahl n eine Primzahl
+ do i = 2 to 99999
-::Wenn gtm = 2 ist, dann ist die zu prüfende Zahl n eine ganz gewöhnliche Zahl
+   fpsprb.i = " "
-::Wenn gtm = 3 ist, dann ist die zu prüfende Zahl n eine Pseudoprimzahl
+   t=0
-::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.
+   t2=0
+   do i2 = 2 to (i-2)
+     call m_u i2, (i-1), i
+     pt = result
+     if (pt = 1) then do
+                         t = 1
+                         fpsprb.i2 = fpsprb.i2||i||", "
+     end
+     if (pt > 1) then t2 = 1
+   end
+   tg = t + t2
+   if (tg = 2) then do
+                      anzfpspr = anzfpspr + 1
+                      ausgabe = "fpspr."||anzfpspr||" = "||i
+                      say ausgabe
+                      lineout("epspr_var.txt",ausgabe)
+   end
+ end
+ lineout("fpsprb_table2.txt","{| {{prettytable}")
+ do i = 2 to 99999
+   ausgabe = "|"||i||" ||"||fpsprb.i||"@"
+   say ausgabe
+   lineout("fpsprb_table2.txt",ausgabe)
+   lineout("fpsprb_table2.txt","|-")
+ end
+</code>
-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.
+The File "epspr_var.txt" is used to calculate euler pseudoprimes. The file "fpsprb_table2.txt" is a table in Wikimedia format.
-[[Kategorie:Zahlentheorie]]
-== Init-Quelle ==
+The List:
-Entnommen aus der:
+<code>
-[http://de.wikipedia.org/wiki/Fermatscher_Primzahltest_(Programm-Code) Wikipedia]
+ fpspr.1 = 15
+ fpspr.2 = 21
+ fpspr.3 = 25
+ fpspr.4 = 28
+ fpspr.5 = 33
+ fpspr.6 = 35
+ fpspr.7 = 39
+ fpspr.8 = 45
+ fpspr.9 = 49
+ .
+ .
+ .
+ fpspr.5974 = 11620
+ fpspr.5975 = 11623
+ fpspr.5976 = 11625
+ fpspr.5977 = 11627
+ fpspr.5978 = 11629
+</code>
-Autoren: Riemanns Freund , YMS , Andreas aus Hamburg in Berlin, Revolus, Nuuk, Kubieziel, Bananeweizen, P. Birken, Srbauer, Arbol01, Markus Schweiß
+will be generate as "epspr_var.txt" by the following Souerce code to calculate the fermat pseudoprimes:
-{{Link_LD_fehlt}}
+<code>
-[[Kategorie:WikiPedia Deleted]]
+ /* Ein REXX-Programm */
+ call load 'mod_up.r'
+ anzfpspr=0
+ do i = 2 to 99999
+   fpsprb.i = " "
+   t=0
+   t2=0
+   do i2 = 2 to (i-2)
+     call m_u i2, (i-1), i
+     pt = result
+     if (pt = 1) then do
+                         t = 1
+                         fpsprb.i2 = fpsprb.i2||i||", "
+     end
+     if (pt > 1) then t2 = 1
+   end
+   tg = t + t2
+   if (tg = 2) then do
+                      anzfpspr = anzfpspr + 1
+                      ausgabe = "fpspr."||anzfpspr||" = "||i
+                      say ausgabe
+                      lineout("epspr_var.txt",ausgabe)
+   end
+ end
+ lineout("fpsprb_table2.txt","{| {{prettytable}")
+ do i = 2 to 99999
+   ausgabe = "|"||i||" ||"||fpsprb.i||"@"
+   say ausgabe
+   lineout("fpsprb_table2.txt",ausgabe)
+   lineout("fpsprb_table2.txt","|-")
+ end
+</code>

Fermatscher Primzahltest (Programm-Code): Unterschied zwischen den Versionen

Version vom 13. Dezember 2009, 14:06 Uhr

Navigationsmenü

Suche