Pseudoprimzahlen: Programme

Aus Wikibooks

Inhaltsverzeichnis

1 Carmichael-Zahlen
- 1.1 zweiter Ansatz
- 1.2 Carmichael-Zahlen nach Chernick
2 absolute Eulersche Pseudoprimzahlen
3 Mod_Up
4 Fermatsche Pseudoprimzahlen

[Bearbeiten] Carmichael-Zahlen

Ein Programm, das eine Liste von Carmichael-Zahlen ausgibt, ist geradezu trivial. Das dem so ist, verdanken wir dem Kriterium von Korselt. Dieses Theorem besagt, das eine Carmichel-Zahl $c\$ eine quadratfrei, aus mindestens drei Primfaktoren bestehende, natürliche Zahl der Form $c = p_1\cdot p_2\cdot ... \cdot p_n\$ ist, so das für jedes $p_i\$ gilt, das $p_i - 1\$ die Zahl $c - 1\$ teilt. Daraus folgt, das man sich um den kleinen fermatschen Satz $a^{n-1} \equiv 1 \mod n$ nich im geringsten zu kümmern braucht. Neben Korselts Kriterium gibt es auch noch Formeln zum erzeugen spezieller Carmichael-Zahlen. Auch bei diesen Beispielen braucht man sich um den kleinen fermatschen Satz nicht zu kümmern.

[Bearbeiten] zweiter Ansatz

Das folgende Programm benutzt drei ineinander verschachtelte Schleifen, durch die sichergestellt wird, das drei zueinander teilerfremde Primzahlen ausgewählt werden. Aus diesen drei Primzahlen wird ein Produkt gebildet, das die zu testende Zahl darstellt. An dieser Zahl wird nun Korselts Kriterium getestet, was einfach ist, da dem Programm die zu der zu testenden Zahl zugehörigen Primteiler bekannt sind. Ist Korselt Kriterium erfüllt, dann handelt es sich bei der Zahl um eine Carmichael-Zahl, und die Zahl wird, samt Primzahlfaktoren als Carmichael-Zahl ausgegeben.

Details: Die Variable p.0 einthält die Anzahl der unterschiedlichen Primzahlen. In p.1 bis p.(p.0) sind die einzelnen Primzahlen abgelegt.

p.1  = 3
p.2  = 5
p.3  = 7
p.4  = 11
p.4  = 13
p.5  = 17
p.6  = 19
p.7  = 23
p.8  = 29
p.9  = 31
p.10 = 37
.
.
.
p.549 = 4001
p.550 = 4003
p.551 = 4007
p.552 = 4013
p.553 = 4019
p.554 = 4021
p.555 = 4027
p.556 = 4049
p.557 = 4051
p.558 = 4057
i=558
do a=1 to (i-2)
  do b=a+1 to (i-1)
    do c=b+1 to i
      t = 0
      z=p.a*p.b*p.c
      ax=p.a-1
      bx=p.b-1
      cx=p.c-1
      zax=(z/p.a)-1
      zbx=(z/p.b)-1
      zcx=(z/p.c)-1
      pz=(zax // ax) + (zbx // bx) + (zcx // cx)
      if (pz = 0) then t = 1
      if (t = 1) then do
        say z||"="||p.a||"*"||p.b||"*"||p.c
        lineout("rcrmn___.txt",z||" = "||p.a||"*"||p.b||"*"||p.c)
      end
      t=0
    end
  end
end

Das Programm kann man modifizieren, indem man die Anzahl der Prizahlen erhöht. Für Carmichel-Zahlen mit mehr als drei Primfaktoren muß man die Anzahl der Schleifen erhöhen, und die Prüfroutinen erweitern.

[Bearbeiten] Carmichael-Zahlen nach Chernick

Die Carmichel-Zahlen nach Chernick sind nur ein kleiner Ausschnitt aus den Carmichael-Zahlen. Sie lassen sich durch folgende Formel generieren: $M_3(n) = (6n+1)\cdot (12n+1)\cdot (18n+1)\$ . Es gibt dabei allerdings zwei Einschränkungen:

keine der drei Terme $(6n+1)\$ , $(12n+1)\$ und $(18n+1)\$ darf eine Quadratzahl ergeben, der ganze Ausdruck $M_3(n) = (6n+1)\cdot (12n+1)\cdot (18n+1)\$ muß quadratfrei sein.
Jede der drei Terme $(6n+1)\$ , $(12n+1)\$ und $(18n+1)\$ muß eine Primzahl sein. Halt, hier gibt es eine Ausnahme: Wenn eine einzige der drei Terme eine fermatsche Pseudoprimzahl oder selbst eine Carmichael-Zahl ist, so ist $M_3(n)\$ trotzdem eine Carmichael-Zahl.

Alle gültigen $n\$ für eine Carmichael-Zahlen nach Chernick enden mit einer 0, einer 1 einer 5 oder einer 6.

l.1  = 0
l.2  = 1
l.3  = 5
l.4  = 6
do i = 0 to 1000
  do j = 1 to 4
    n=i+l.j
    m=(6*n+1)*(12*n+1)*(18*n+1)
    if((primzahl(6*n+1)=true) && (primzahl(12*n+1)=true) && (primzahl(18*n+1)=true)) then do
      say m||"="||(6*n+1)||"*"||(12*n+1)||"*"||(18*n+1)
      lineout("rcrmn___.txt",m||" = "||(6*n+1)||"*"||(12*n+1)||"*"||(18*n+1))
    end
  end
end

Das Programm läßt sich entsprechend der Formeln für Carmichael-Zahlen nach Chernick, mit mehr als drei Primzahlfaktoren, nach der entsprechenden Formel erweitern.

[Bearbeiten] absolute Eulersche Pseudoprimzahlen

Das Programm, mit dem oben Carmichael-Zahlen erzeugt werden, kann man mit einer kleinen Modifikation dazu bringen, absolute eulersche Pseudoprimzahlen zu erzeugen:

      zax=(z-1)/2
      pz=(zax // ax) + (zax // bx) + (zax // cx)

statt

      zax=(z/p.a)-1
      zbx=(z/p.b)-1
      zcx=(z/p.c)-1
      pz=(zax // ax) + (zbx // bx) + (zcx // cx)

Das hierbei alle absoluten eulerschen Pseudoprimzahlen ausgegeben werden, ist eine andere Frage. Aber die Zahlen, die ausgegeben werden, sind absolute Eulersche Pseudoprimzahlen.

[Bearbeiten] Mod_Up

Da man es bei der Berechnung von fermatschen Pseudoprimzahlen häufig mit großen Potenzen großer Zahlen zu tun bekommt, hat man ein kleines Problem. Zum Beispiel für den Nachweis, das 341 eine fermatsche Pseudoprimzahl zur Basis 2 ist, muß man die Zahl $2^{340}\$ berechnen. Diese Zahl heißt ausgeschrieben:

2239744742177804210557442280568444278121645497234649534899989100963791871180160945380877493271607115776

Das ist für ein Programm wie MuPad wahrscheinlich kein Problem, für die meisten herkömmlichen Programmiersprachen aber sehr wohl. Durch eine Kombination von Multiplikation und Modulo kann man aber auch wesentlich größere Potenten kleinhalten.

Beispiel: $5^6 = 15625\$ >. Letztendlich interessiert uns ja aber nicht $5^6 = 15625\$ , sondern vielmehr $5^6 \mod n$ mit sagen wir mal $n = 7\$ . Das ist $5^6 \mod 7 = 1\$ . Nun läßt sich $5^6 \mod 7\$ auch so ausdrücken:

$(((((((((5 * 5) \mod 7) * 5) \mod 7) * 5) \mod 7) * 5) \mod 7) * 5) \mod 7$

Dabei wird der Wert 7 niemals überschritten.

/* 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

[Bearbeiten] Fermatsche Pseudoprimzahlen

Eine Primzahl unterscheidet von fermatschen Primzahlen und Carmichael-Zahlen dadurch, das der kleine fermatsche Satz $a^{n-1} \equiv 1 \mod n$ für alle Basen $a\$ mit $2 \le a < n$ gilt. Carmichael-Zahlen unterscheiden sich von normalen Pseudoprimzahlen das der Anteil von Basen $a\$ mit $2 \le a < n$ für die $a^{n-1} \equiv 1 \mod n$ gilt, größer gleich 97% beträgt. Der einfachheithaber benutzt man als als Basen $a\$ nur die Primzahlen die kleiner als die zu testende Zahl $n\$ ist. Das Programm testet also zu jeder Primbasis $a\$ ob eine Zahl $n\$ die Bedingung $a^{n-1} \equiv 1 \mod n$ erfüllt. Erfüllt sie es, dann wird die Variable tm1 = 1 gesetzt, und gleichzeitig die Zählvariable tm3 um eins erhöht. Erfüllt die Zahl $n\$ die Bedingung nicht, dann wird die Variable tm2 = 2 gesetzt. Nach ablauf der Tests wird die Variable gtm = tm1 + tm2 gesetzt. Aus gtm und dtm läßt sich ablesen, ob es sich bei der Zahl $n\$ um eine Primzahl, eine fermatsche Pseudoprimzahl oder eine Carmichael-Zahl handelt.

gtm	dtm	Art der Zahl
1	-	Primzahl
3	tm3 < dtm	fermatsche Pseudoprimzahl
3	tm3 >= dtm	Carmichael-Zahl

/* 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);
} 

int 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);
  return 0;
}

Nachteil des Programms: Es wird schnell sehr langsam. Ausserdem ist es für einige Pseudoprimzahlen blind. So besitzt die Zahl 39 keine Primzahlen $p\ < 39$ zu denen die 39 pseudoprim wäre.

Pseudoprimzahlen: Programme

Aus Wikibooks

Inhaltsverzeichnis

[Bearbeiten] Carmichael-Zahlen

[Bearbeiten] zweiter Ansatz

[Bearbeiten] Carmichael-Zahlen nach Chernick

[Bearbeiten] absolute Eulersche Pseudoprimzahlen

[Bearbeiten] Mod_Up

[Bearbeiten] Fermatsche Pseudoprimzahlen

Ansichten

Persönliche Werkzeuge

Navigation

Suche

Mitmachen

Werkzeuge

Drucken/exportieren