Nehmen wir einmal an, wir haben eine ziemlich große Zahl gegeben,
beispielsweise 123456790120987654369. Wir möchten nun wissen, ob
dies eine Primzahl ist oder nicht. Das ist eigentlich unser
einziges Problem, um das es in diesem Artikel gehen wird. Zunächst
einmal sollten wir jedoch klarstellen, was unter einer Primzahl zu
verstehen ist. Das ist eine Zahl, die nur durch 1 und sich selbst
ohne Rest teilbar ist. Damit haben wir zwar nicht die allgemeine
korrekte Definition gegeben, für den Bereich der ganzen Zahlen
stimmt sie mit derselben aber überein. Erwähnt werden soll noch,
daß die 1 nicht zu den Primzahlen gerechnet wird.
Als Beispiele betrachten wir die Zahlen 6 und 7. 6 ist sicher
keine Primzahl, da 6=2*3 gilt. Hingegen kann eine derartige
Gleichung für 7 nicht angegeben werden, somit ist 7 prim. Wir
können also nachprüfen, ob eine Zahl prim ist, indem wir Teiler
der Zahl suchen. Finden wir welche, ist die Zahl nicht prim.
Finden wir keine, ist sie prim. Hierzu müssen wir aber wissen, wie
lange wir suchen müssen, bis wir zu dem Schluß gelangen können,
daß eine Zahl x prim ist.
Nun, zeigt sich, daß die Zahlen von 2 bis zur Wurzel aus x als
Teiler in Frage kommen. Dies ist eine Folge davon, daß es zu jedem
Teiler, der größer als die Wurzel ist, einen zweiten, kleineren
gibt. Zum Nachweis, daß die Zahl x prim ist, genügt es also, alle
Zahlen von 2 bis sqrt(x) zu inspizieren. Dies wird in einer
Schleife geschehen. Wenn wir die 2 einzeln testen, können wir
dabei sogar die geraden Zahlen auslassen.
Damit ist die Strategie klar. Kommen wir zu der eingangs
betrachteten Zahl zurück. Wollen wir testen, ob diese prim ist,
müssen wir alle geraden Zahlen bis zur Wurzel auf Teilerschaft
überprüfen. Kein Problem, wir haben ja einen Computer! Die
(ganzzahlige) Wurzel hat den Wert 11111111111. Es ist nicht
einfach, festzustellen, wie lange ein bestimmter Rechner mit
dieser Aufgabe beschäftigt wäre. Eins steht jedoch fest: Es gibt
wohl keinen PC-Besitzer, der nicht irgendwann die Geduld verlöre
und den Vorgang abbräche.
Fazit: Obwohl unsere Zahl mit 21 Stellen nicht einmal übermäßig
groß ist, ist eine Überprüfung aller Teiler durch einen Micro-
Computer ausgeschlossen. Bei noch größeren Zahlen, etwa um 100
Stellen, müssen selbst Großrechenanlagen und Vektorrechner
kapitulieren.
Aus der Geschichte
Fragen wir nun nach dem Zweck derartiger Betrachtungen. Wer hat
überhaupt ein Interesse, solche Zahlen als prim zu erkennen? Die
erste Antwort ergibt sich aus dem Artikel
Lange Integer-Zahlen in C.
Dort haben wir den RSA-Algorithmus programmiert. Wir sind bei
ernsthafter Anwendung darauf angewiesen, große Primzahlen zu
finden.
Zum anderen ist es der reine menschliche Forschergeist, der lange
vor der Entdeckung dieses Verfahrens Mathematiker beschäftigte. So
vermutete der französische Mathematiker Pierre de Fermat (1601-
1665), daß der Ausdruck 2^(2^k)+1 für alle natürlichen Zahlen k
eine Primzahl ergibt. Bis k=4 war das zweifellos richtig, jedoch
bereits bei k=5 stimmt die Vermutung nicht. Schlimmer noch: Bis
heute wurde kein weiterer Wert für k gefunden, bei dem sich eine
Primzahl ergeben hätte. Somit ist unbekannt, ob es überhaupt einen
Wert gibt, bei dem dies der Fall wäre.
Ob man Fermat weiterhin widerlegen will, oder ob man eine neue
Fermatsche Primzahl finden will - Auf jeden Fall ist man auf das
Rechnen mit großen Zahlen und die Benutzung wesentlich schnellerer
Primzahltests angewiesen. Denn bereits die achte Fermat-Zahl hat
77 Stellen, da spielt kein Rechner mehr mit, und wäre er noch so
schnell.
Aus Frankreich stammte auch der Mathematiker Martin Mersenne
(1558-1648). Er war vorsichtiger als Fermat und vermutete daher
nur, daß die Formel 2^p-1, wobei p selbst prim sein muß, "meist"
Primzahlen ergeben sollte. Zwar ist auch das Wort "meist" noch
hoffnungslos übertrieben, aber immerhin stimmt die Aussage für 24
Zahlen p unterhalb von 20000.
Z.B. wissen wir seit Anfang dieses Jahrhunderts, daß eine dieser
Zahlen, nämlich 2^67-1, nicht prim ist. Der Amerikaner Frank Cole
hat zu dieser Feststellung drei Jahre lang seine Freizeit benutzt
und konnte schließlich die Faktoren 193707721 und 761838257287
angeben. Drei Jahre sind uns natürlich ein zu großer Aufwand, und
wir wollen später sehen, ob wir dieses Resultat auch schneller
erzielen können.
Die Bemühungen Fermats und Mersennes jedenfalls hatten zum Ziel,
eine Formel zu finden, die immer Primzahlen liefert, oder die oft
Primzahlen liefert, oder auch eine Formel, die alle Primzahlen
liefert.
Rein sportlichen Charakter hat die Jagd nach "Rekordprimzahlen",
d.h. der größten Zahl, die als prim erkannt ist. Momentan ist dies
die Zahl 2^132049-1, also auch eine vom Mersenne-Typ. Sie hat
39751 Stellen und wurde auf einer Cray-XMP berechnet, natürlich
mit Hilfe spezieller Primzahltests.
Damit wären wir wieder beim Thema. Zunächst ein Wort zur
Literatur. In [1] wird ein Überblick über alle Bereiche der
Primzahltests und Zerlegungsmethoden gegeben, ohne zu sehr ins
(mathematische) Detail zu gehen. Der Artikel ist somit auch für
nicht-studierte Mathematiker verständlich, sofern ein gewisses
Interesse aufgebracht wird. Wer tiefer in die Materie einsteigen
will, findet dort ein ausführliches Literaturverzeichnis.
Ein wenig Theorie
Auch wir wollen hier keine schwierigen Beweise geben, doch ein
wenig Theorie ist sicher interessant. Viele Primzahltests gehen
nämlich auf den Kleinen Fermatschen Satz zurück, der lautet:
Kleiner Fermatscher Satz:
Für eine Primzahl n und eine beliebige Zahl a gilt: a^(n-1) mod n = 1,
sofern a nicht Vielfaches von n ist.
|
Das hört sich zunächst recht brauchbar an. Leider gibt es jedoch
auch Zahlen, für die diese Bedingung gilt, die jedoch keine
Primzahlen sind. Nach deren Entdecker werden sie Carmichael-Zahlen
genannt. Die kleinste davon ist 561=3*11*17. Unser Satz kann also
nur dazu dienen, Zahlen als zusammengesetzt zu erkennen. Finden
wir nämlich eine Zahl a, die nicht Vielfaches von n ist und für
die die Gleichung a^(n-1) mod n = 1 nicht erfüllt ist, kann n
nicht prim sein.
Will man andersherum zeigen, daß eine Zahl prim ist, muß man sich
etwas mehr überlegen. Am einfachsten macht man es sich in der
Forderung von speziellen Eigenschaften der zu untersuchenden Zahl.
Damit kann man zwar nicht alle Zahlen behandeln, hat aber meist
nur einfache Bedingungen zu testen. Exemplarisch wollen wir hierzu
den Satz von Brillhart und Selfridge angeben. Dieser funktioniert
für Zahlen n, bei denen die Primfaktorzerlegung von n-1 bereits
bekannt ist. Er lautet:
Satz von Brillhart und Selfridge:
Eine Zahl n ist prim, wenn für jeden Primteiler p von n-1 eine
Zahl a existiert mit den Eigenschaften:
a^((n-1)/p) mod n != 1 und a^(n-1) mod n = 1.
|
Wir sehen hier die Verwandtschaft zum Kleinen Fermatschen Satz,
der ja identisch zu der zweiten Bedingung ist. Wie können wir
diesen Satz in der Praxis verwenden? Nun, keinesfalls sollten wir
ihn für beliebige Zahlen benutzen, denn dann müßten wir die
Primfaktorzerlegung von n-1 berechnen, was ziemlich lange dauern
kann.
Anwendung bei Primzahltests
Eine sinnvolle Anwendung ist der Test von Zahlen bestimmter
"Bauart". Bei diesen sollte die Zerlegung von n-1 direkt abzulesen
sein. Etwa wären das Zahlen der Form 2^k+1. In diesem Fall müßten
die beiden Bedingungen nur für eine einzige Zahl, nämlich 2,
überprüft werden, zweifellos ein entscheidender Vorteil. Geeignet
sind aber auch Zahlen 2^k*q^j+1. Hierbei ist q eine Primzahl
ungleich 2, zu testen wären also jeweils zwei Faktoren 2 und q.
Klar ist, daß die 2 immer Teiler von n-1 sein muß, sonst wäre n ja
gerade und damit nicht prim.
Zunächst wirft der Satz eine Frage auf, nämlich nach den Werten
von a. Es muß ein a existieren, für das die Bedingungen erfüllt
sind. Keine Aussage wird darüber gemacht, welche a hierfür
geeignet sind. Und in der Tat ist diese Frage bisher ungeklärt. In
der Praxis hat sich aber gezeigt, daß der Test bei Verwendung von
kleinen Zahlen a=2,3,4,... bereits funktioniert. Meistens müssen
mehrere Werte überprüft werden, bis eine Entscheidung "prim" oder
"nicht prim" getroffen werden kann.
Nehmen wir nun an, wir wollen für einen Primteiler p von n-1 und
eine Zahl a den Test durchführen. Wie gehen wir vor? Zunächst
berechnen wir a^((n-1)/p) mod n, welches in der ersten Bedingung
auftritt. Dies nennen wir einmal w. Zwei Fälle sind möglich.
Entweder w ist gleich 1, oder w ist ungleich 1. Im ersten Fall ist
die Bedingung nicht erfüllt, daher ist dieses a nicht geeignet,
wir können gleich zur Überprüfung des nächsten Werts für a
übergehen. Im zweiten Fall können wir mit der Prüfung der zweiten
Bedingung fortfahren.
Wir müssen nun nicht mehr a^(n-1) mod n von Grund auf berechnen,
sondern können w benutzen. Denn w^p mod n liefert uns den
gewünschten Wert. Ist dieser gleich 1, haben wir unser Ziel
erreicht, a hat den Test bestanden. Ist der Wert jedoch ungleich
1, wissen wir immerhin, daß n keine Primzahl ist. Denn diese
Bedingung ist ja identisch zum Kleinen Fermatschen Satz, muß also
für Primzahlen unbedingt erfüllt sein.
Dieses Verfahren müssen wir für alle Primteiler p von n-1 und
verschiedene Werte für a durchführen. Dies ist die Realisierung
dieses Verfahrens:
#define MaxNr 50
#include "longcalc.c"
void main()
{
long e,e1,e2;
scanf("%ld %ld",&e1,&e2);
for (e=e1;e<=e2;e++) {
printf("%ld : ",e); p3test(5L,e); printf("\n"); }
}
/* Prueft, ob n=2^e+1 prim ist. Das Resultat wird auf den Bildschirm
geschrieben. Ist n prim, wird vorher der Parameter ausgegeben, fuer
den das Brillhart-Selfridge-Kriterium erfuellt ist. */
void p2test(long e)
{
long a,t;
longint el,n;
longl(e,el); powl(zweil,el,n); incl(n);
for (a=2;a<30;a++) {
t=bs_check(2L,n,a);
if (t==1) { printf("nicht prim"); return ; }
if (t==2) { printf("%ld - prim",a); return; } }
printf("unentscheidbar"); return;
}
/* Prueft, ob n=2^e*3^f+1 prim ist. Das Resultat wird auf den
Bildschirm geschrieben. Ist n prim, werden vorher die Parameter
ausgegeben, fuer die das BS-Kriterium erfuellt ist. */
void p3test(long e,long f)
{
long a,t;
longint el,fl,n,h;
longl(e,el); longl(f,fl);
powl(zweil,el,h); powl(dreil,fl,n); multl(h,n,n); incl(n);
for (a=2;a<30;a++) {
t=bs_check(2L,n,a);
if (t==1) { printf("nicht prim"); return; }
if (t==2) { printf("%ld ",a); goto L1; } }
printf("unentscheidbar"); return;
L1: for (a=2;a<30;a++) {
t=bs_check(3L,n,a);
if (t==1) { printf("nicht prim"); return; }
if (t==2) { printf("%ld - prim",a); return; } }
printf("unentscheidbar"); return;
}
/* p sei ein Primfaktor von n. Es wird geprueft, ob die Zahl a das
Brillhart-Selfridge-Kriterium erfuellt. Ausgabe: 0, wenn eine
Entscheidung nicht moeglich ist; 1, wenn n nicht prim; 2, wenn
das Kriterium erfuellt ist. */
void bs_check(long p, longint n, long a)
{
longint pl,al,w,ex;
longl(p,pl); longl(a,al);
transl(n,ex);
decl(ex);
divl(ex,pl,ex);
ahsmodn(al,ex,n,w);
if (eql(w,einsl)) return 0;
ahsmodn(w,pl,n,w);
if (eql(w,einsl)) return 2; else return 1;
}
|
Wir sorgen also als erstes für die Einführung
des Datentyps longint, den wir im Artikel
Lange Integer-Zahlen in C
zusammen mit den
nötigen Routinen implementiert haben. Nötig ist die Angabe der
Länge einer longint-Zahl. Setzen wir MaxNr auf 50, verfügen wir
über 466 Stellen (50 mal Zehnerlogarithmus von 2^31).
Die wichtigste Prozedur ist bs_check. Sie führt den eben
beschriebenen Test nach Brillhart und Selfridge durch. Dies für
eine Zahl n, einen Primfaktor p von n-1 und eine beliebige Zahl a.
n muß vom Typ longint sein, p und a vom Typ long. Beide werden in
eine longint-Zahl umgewandelt und heißen dann pl und al. In der
Variablen ex wird der Exponent unseres ersten Ausdrucks
zusammengestellt, das ist (n-1)/p. Mit ahsmodn wird dieser dann
berechnet und w zugewiesen. Ist w gleich 1, wird 0 zurückgegeben.
Dies soll heißen, eine Entscheidung ist aufgrund dieser Zahl a
nicht möglich.
Ist w ungleich 1, wird w^p mod n berechnet. Ist dies nun gleich 1,
ist die Bedingung erfüllt. Um das anzuzeigen, geben wir die
Codezahl 2 zurück. Im anderen Fall kann n keinesfalls prim sein,
dies kennzeichnen wir durch die Rückgabe von 1.
Im Anwendungsfall müssen wir mindestens einen Faktor p, aber meist
mehrere Zahlen a auf diese Weise durchtesten. Hierfür müssen
weitere Unterprogramme geschrieben werden. Beginnen wir mit
p2test. Dies testet eine Zahl 2^e+1. Der Exponent e wird als long-
Zahl übergeben. Nun müssen wir zunächst den Wert von n berechnen.
In der darauf folgenden Schleife wird bs_check für verschiedene
Werte a aufgerufen. Als Primfaktor wird natürlich jedesmal die 2
angegeben.
Ist der Rückgabewert gleich 1 oder 2, wird das entsprechende
Ergebnis auf den Bildschirm geschrieben. Der Wert für a, der das
Kriterium erfüllte, erscheint dort ebenfalls. Ist t hingegen 0,
muß ein weiterer Wert für a probiert werden. Nun kann es
passieren, daß die Schleife durchlaufen wird, ohne daß ein a das
Kriterium erfüllt, aber auch n nicht als zusammengesetzt erkannt
wird. Dann bleibt nur die Möglichkeit, die Obergrenze der Schleife
zu erhöhen oder einen anderen Test auszuwählen. Etwas derartiges
ist in der praktischen Erprobung allerdings nicht aufgetreten.
Die Routine p3test eignet sich zur Überprüfung einer Zahl
2^e*3^f+1. Sie funktioniert ganz ähnlich wie p2test, jedoch werden
hier zwei Primfaktoren getestet, 2 und 3. Dies muß in zwei
verschiedenen Schleifen geschehen, da die Werte für a bezüglich
der beiden Faktoren nicht identisch sein müssen. Beide Werte, die
sich beim Test ergaben, erscheinen auch auf dem Bildschirm, falls
n prim ist. Soll p3test für eine andere Primzahl als 3 benutzt
werden, müssen zwei ßnderungen erfolgen: Zum einen bei der
Berechnung von n beim zweiten powl-Aufruf, zum anderen beim
zweiten Aufruf von bs_check.
Das Hauptprogramm muß jeweils den eigenen Bedürfnissen angepaßt
werden. Hier werden Zahlen der Form 2^5*3^e+1 getestet. e stammt
aus dem Bereich zwischen e1 und e2, diese Zahlen werden vom
Benutzer erfragt. Die Resultate werden von p3test auf den
Bildschirm geschrieben.
Das Verfahren nach Brillhart und Selfridge eignet sich zum Finden
von Rekordprimzahlen. Die Funktion p2test ist hierfür vielleicht
nicht ganz so günstig, denn hiermit ergaben sich nur die 5 bereits
bekannten Fermatschen Zahlen 2^e+1 bei e=1, 2, 4, 8 und 16. Die
letztere hat nur fünf Stellen, dies kann mit jedem Taschenrechner
nachvollzogen werden.
Interessantere Resultate ergaben sich beim Durchrechnen von Reihen
der Form 2^k*3^e+1 mittels p3test. Die größten hierbei gefundenen
Primzahlen sind 2^3*3^130+1, 2^3*3^143+1 und 2^4*3^195+1. Die
letzte dieser drei ist immerhin 95 Stellen lang. Auch die 5 als
Faktor von n-1 lieferte noch ein beachtenswertes Ergebnis, nämlich
die Zahl 2*5^105+1, diese ist allerdings um 21 Stellen kürzer.
Will man derartige Resultate erzielen, braucht man meist viel
Geduld. Halten wir uns beispielsweise in der Größenordnung unserer
Rekordprimzahl 2^4*3^195+1 auf, benötigt selbst die Erkenntnis,
daß eine Zahl zusammengesetzt ist, meist mehrere Minuten. Für den
Nachweis, daß sie prim ist, müssen wir sogar eine Viertel- oder
halbe Stunde investieren.
Entsprechend schneller sind Primzahlen in der Größe von 20 bis 30
Stellen zu bekommen. Als besonders dankbar erwies sich die Reihe
2*3^e+1. Im Bereich zwischen e=1 und e=65 wurden 13 Primzahlen
entdeckt, davon vier mit mehr als 20 Stellen, die größte hat sogar
31 Stellen.
Ähnliche Tests wie der von Brillhart und Selfridge gibt es für die
Fälle, in denen die Zerlegung von n+1, n^2+1 oder etwa n^2+n+1
bekannt ist. Auch wurden knifflige Verfahren konstruiert, in denen
nur eine teilweise Zerlegung dieser Zahlen bekannt sein muß. Beide
Sorten werden unter dem Begriff "Lucas-Lehmer-Tests"
zusammengefaßt.