Der Algorithmus hat folgenden Ablauf:
Hier liegt die Wahrscheinlichkeit, daß ein zufällig gewähltes a Zeuge dafür ist, daß p zusammengesetzt ist, nicht unter 50 Prozent. Diesen Test wiederholt man t-mal. Liefert die Berechnung 1 oder -1, aber nicht immer den Wert 1, so ist p wahrscheinlich prim und die Fehlerwahrscheinlichkeit liegt bei 1 zu 2t.
/* Datei mit der Funktion main
Hier wird die Schnittstelle zwischen User und Computer realisiert */
# include <stdio.h>
# include <conio.h>
# include "funk.h"
# include "lehmann.h"
void main (void)
{
unsigned long primzahl;
char abfrage;
int ergebnis,abbruch;
abbruch = False;
while(abbruch == False) /* Schleife fuer mehrmaliges durchlaufen des
Programms */
{
clrscr();
printf("geben Sie eine Zahl zwischen 0 und 4294967295 ein :");
scanf(" %lu",& primzahl); /*Primzahleingabe*/
ergebnis = Lehmann (primzahl);/* Aufruf der Testalgorithmus-Funktion
Uebergabeparameter:
zuvor eingegebene Primzahl*/
if (ergebnis == True)/* Abfrage ob Zahl eine Primzahl ist*/
{
printf("\n\n\n\n\n\tdie von Ihnen gewählte Zahl %d ist mit einer ",
primzahl);
printf("\n\tFehlerwahrscheinlichkeit von 1: 2^%d eine
Primzahl",Wiederholtest);
} else
printf("\n\n\n\n\tdie von Ihnen gewählte Zahl ist keine primzahl");
printf("\n\n Wollen Sie eine weitere Zahl testen? [y,n]")
abfrage = getch();
switch (abfrage) /* Abfrage ob programm wiederholt werden soll */
{
case 'y':
case 'Y': abbruch = False;
break;
default : abbruch = True;
break;
}
}
}
Datei lehmann.h
/* Headerdatei fuer die Datei lehmann.c */
#define False 0
#define True 1
#define Wiederholtest 30000 /* definiert wie oft der Testalgorithmus
durchlaufen werden muss */
int Lehmann (unsigned long p); /* Prototyp fuer die
Testalgorithmus-Funktion*/
Datei Lehmann.c
/* Datei beinhaltet den Testalgorithmus fuer die Primzahlen */
# include <stdlib.h> /*Wird fuer Zufallszahlgenerierung benoetigt*/
# include <stdio.h>
# include <time.h> /*Wird fuer Zufallszahlgenerierung benoetigt*/
# include "lehmann.h"
# include "funk.h"
int Lehmann (unsigned long p)
{
int abbruch = False;
int a,erg_potenz,erg_1,erg_neg1,wiederholung,zaehler;
unsigned long prim;
zaehler = 0;
a = 0;
prim = p;
wiederholung = 0;
randomize();
while ( wiederholung < Wiederholtest && abbruch == False)
/* Pruefalgorithmus wird maximal solange wiederholt, wie es in Wiederholtest
definiert ist. Er wird vorzeitig abgebrochen wenn erg_potenz ungleich erg_1
und erg_neg1 */
{
if (prim == 1)
a=1; /* Abfrage, da wenn prim = 1 normalerweise a = 0.
Wenn jedoch a = 0 dann funktioniert der
Algorithmus nicht*/
while (a==0) /* Zufallszahlgenerierung mit der Voraussetzung daß
Zufallszahl ungleich 0*/
{
if (prim < 32767)
a = random (prim);
else
a = random (32767);
}
erg_potenz = potenz (a,(prim-1)/2,prim);
/* Berechnung von a^(prim-1)/2 modulo prim */
erg_1 = 1 % prim; /* Berechnung von 1 modulo prim */
erg_neg1 = (-1%(int)prim); /* Berechnung von -1 modulo prim */
erg_neg1 += prim; /*Korrektur fuer modulare Rechnung mit neg. Zahlen*/
if ((erg_potenz == erg_1) || (erg_potenz == erg_neg1))
/*Abfrage ob erg_potenz gleich erg_1 oder erg_neg1*/
{
wiederholung++; /*zaehlen der Algorithmuswiederholungen*/
if (erg_potenz == erg_1)
zaehler++; /* zaehlen wie oft bei den Wiederholungen
a^(prim-1)/2 modulo prim = 1 modulo prim*/
} else
abbruch = True; /* Vorzeitiger Abbruch der Algorithmusdurchlaeufe
daraus folgt daß Testzahl definitiv
keine Primzahl */
}
if ((abbruch == False) && (zaehler != wiederholung))
/*Abfrage ob Primzahl oder nicht*/
return (True);
else
return (False);
}
Datei funk.h
/* Datei mit der Funktion zum modularen Potenzieren mit großen
Exponenten*/
unsigned long potenz (unsigned long basis, unsigned long exponent, unsigned
long modulo)
{
unsigned long erg,basis_2,exponent_2;
int i,a;
erg = 1;
basis_2 = basis;
exponent_2 = exponent;
while (exponent_2)
{
a = exponent_2 & 1;
if(a)
erg = (erg*basis_2) % modulo;
exponent_2 >>= 1;
basis_2 = (basis_2*basis_2)%modulo;
}
return(erg);
}
Wenn Sie das Programm prim.exe ausführen, erscheint eine Aufforderung, eine Zahl zwischen 0 und 4294967295 einzugeben.
Sie müssen Ihre Eingabe mit ''RETURN'' bestätigen.
Das programm testet nun mit seinem Algorithmus, ob die eingegebene Zahl mit einer bestimmten Wahrscheinlichkeit eine Primzahl ist. Es gibt zwei Möglichkeiten, was Ihnen das Programm als Ergebnis ausgibt:
Beispiele:
Eingabe:13 Ausgabe:Die von Ihnen gewählte Zahl 13 ist mit einer Fehlerwahrscheinlichkeit von 2 30000 eine Primzahl.
Eingabe:15679 Ausgabe:Die von Ihnen gewählte Zahl 15679 ist mit einer Fehlerwahrscheinlichkeit von 2:30000 eine Primzahl.
Eingabe:793400 Ausgabe:Die von Ihnen gewählte Zahl ist keine Primzahl
Eingabe:6003471 Ausgabe:Die von Ihnen gewählte Zahl ist keine Primzahl
Eingabe 67: Ausgabe:Die von Ihnen gewählte Zahl 67 ist mit einer Fehlerwahrscheinlichkeit von 2:30000 eine Primzahl.