3. Rabin - Miller - Algorithmus

3.1 Allgemeine Beschreibung

Dieser Algorithmus geht auf Michael Rabin und Gary Miller zurück, weshalb er ihren Namen trägt. Der Algorithmus, den ich hier verwendet habe, ist eine vereinfachte Version gegenüber derjenigen, die im DSS-Vorschlag empfohlen wird. Er ist sehr weit verbreitet, weil er so einfach ist.

Bevor man den Algorithmus anwenden kann muß man noch einige Vorbereitungen treffen:

Zuerst erzeugt man eine (möglichst große und ungerade) Zufallszahl p

Dann berechnet man die Zahl b, die angibt wie oft (p-1) durch 2 teilbar ist (2b ist die größte Zweierpotenz, die (p-1) teilt).

Bestimme m so daß die folgende Gleichung erfüllt ist: p=1+2b *m

Nun kann der eigentlich Algorithmus auf p angewendet werden:

1. Bestimme eine Zufallszahl a die kleiner als p ist
2. Setze j=0 und z=am mod p
   • Falls z=1 oder z=p-1, ist p wahrscheinlich eine Primzahl
   • Falls j>0 und z=1, ist p definitiv keine Primzahl

3. Setze j=j+1. Falls j<b und z ≠ p-1 setze z=z2  mod p und gehe (4)

   Falls aber z=p-1, ist p wahrscheinlich eine Primzahl

4. Falls j=b und z ≠ p-1, ist p definitiv keine Primzahl

Die Wahrscheinlichkeit, daß eine nicht-Primzahl den Test trotzdem besteht beträgt 25%. Dabei nimmt aber diese Wahrscheinlichkeit schneller ab als bei den anderen zwei Algorithmen.

In meinem Programm habe ich Schritt 1 so geändert, daß p z.B. bei 100 Tests stets mit unterschiedlichen a getestet wird, und nicht mit denselben nochmal.

Struktogramm Rabin-Miller-Primzahltest

3.2 Source Code

//Primzahltest nach Rabin-Miller
//Autor: Germanos Efthimiadis
//letzte Änderung: 13.1.1998

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

#define MAXINT 32767
#define MAXLONGINT 4294967295l
#define SICHERHEIT 1000l //Anzahl der Tests mit verschiedenen a

//Autor: Bruce Schneier aus Angewandte Kryptographie S.285
//Funktion: mod
//Aufgabe: Berechnung der funktion modulo
//Parameter: unsigned long int a,x,n
//Rückgabe: unsigned long int (a^x mod n)
unsigned long int mod(unsigned long int a,unsigned long int x,unsigned long 
int n)
{
  unsigned long int s,t,u;

  s=1;
  t=a;
  u=x;

  while(u)
  {
    if(u&1)
      s=(s*t)%n;
    u>>=1;
    t=(t*t)%n;
  }
  return(s);
}

//Autor: Germanos Efthimiadis
//Funktion: Zufall
//Aufgabe: Berechnung einer Zufallszahl<Obergrenze
//Paramater: unsigned long int i
//Rückgabe: unsigned long int (Zufallszahl)
unsigned long int Zufall(unsigned long int i)
{
  unsigned long int x,x1,x2,x3;
  x1=(unsigned long int)random(MAXINT);
  x2=(unsigned long int)random(MAXINT);
  x3=(unsigned long int)random(MAXINT);
  x=x1*x2*x3;
  x%=i; // x<i;
  return(x);
}

//Autor: Germanos Efthimiadis
//Funktion: Hauptprogramm
//Aufgabe: Primzahltest nach Rabin-Miller
//Paramater: keine
//Rückgabe: keine
void main (void)
{
  unsigned long int k,y,b,m,j,z

  //In diesem Array werden alle a's gespeichert
  //So wird verhindert, daß man mit demselbem a nochmal prüft
  unsigned long int a[SICHERHEIT];
  unsigned long int p;
  int CursorY,CursorX; //Cursorkoordinaten

  randomize(); //Initialisierung des Z-Generators

  printf("\n\nEs wird eine ungerade Zufallszahl p erzeugt");
  p=Zufall(MAXLONGINT);
  if (p%2==0)
    p--; //Ungerade Zahl
  if (p<1000000000l)
    p+=1000000000l; //10-stellige Zahl
  printf("\np=%lu\n",p);
  printf("\np wird jetzt %lu mal getestet\n",SICHERHEIT);

  b=0; // Wie oft läßt sich p-1 ohne Rest teilen?
  m=p-1;
  while (m%2==0)
  {
    m/=2;
    b++;
  }; //m ergibt sich aus der Berechnung von b

  CursorX=wherex();
  CursorY=wherey();
  for (k=0;k<SICHERHEIT;k++)
  {
    gotoxy(CursorX,CursorY);
    printf("%lu. Test",k+1);
    //Schritt 1
    a[k]=Zufall(p-2);
    y=0;
    while (y<k)
    {
      if (a[k]==a[y]) //Gibt's die Zahl schon?
      {
        a[k]=Zufall(p-2);  //Erzeuge neue Zahl
        y=0; //Beginne Vergleich von vorne
      } else
        y++; //Setze Vergleich fort
    }

    //Schritt 2
    j=0;
    z=mod(a[k],m,p);

    //Schritt 3
    if (!(z==1 || z==p-1))
      goto keine_primzahl;

    //Schritt 4
schritt4:
    if (j>0 && z==1)
      goto keine_primzahl;

    //Schritt 5
    j++;
    if (j<b && z!=p-1)
    {
      z=mod(z,2,p);
      goto schritt4;
    }

    if (z!=p-1)
      goto keine_primzahl;

    //Schritt 6
    if (j!=b || z==p-1)
    {
      printf("\n%lu ist eine Primzahl",p);
      return;
    }
keine_primzahl:
  printf("\n%lu ist keine Primzahl",p);
  return;
}