Die Computerseite von Eckart Winkler
Primzahltests und Primfaktorzerlegung - Teil 1

 

Dieser Artikel ist im Heise-Verlag in der Zeitschrift "c't", Ausgabe 05/1989 erschienen. Er ist hier aus Gründen der besseren Übersicht dreigeteilt. Grundlage ist der Artikel "Lange Integer-Zahlen in C". Links:



Primzahlen

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.


 

Übersicht Programmiersprache C Index