Die Jagd nach großen Primzahlen


Die größte bekannte Primzahl

Bekanntlich ist eine Primzahl eine von 1 verschiedene natürliche Zahl, die keine Teiler außer 1 und sich selbst hat. Schon in der Antike wußten griechische Mathematiker, daß sich jede natürliche Zahl eindeutig (bis auf die Reihenfolge der Faktoren) in ein Produkt von Primzahlen zerlegen läßt und daß es unendlich viele verschiedene Primzahlen gibt. Im Buch IX der Elemente des Euklid (um 300 v. Chr.) findet sich nämlich der folgende Widerspruchsbeweis: Nimmt man an, daß es nur endlich viele Primzahlen gibt, also etwa p1, p2, ... pn, dann ist die Zahl m=p1*p2* ... *pn+1 größer als alle diese Primzahlen und wird von keiner Primzahl geteilt. Also ist m selbst eine Primzahl, ein Widerspruch zur Annahme.

Mit Hilfe des Siebverfahrens des Eratosthenes (um 200 v. Chr.) kann man im Prinzip folgendermaßen nach und nach jede Primzahl finden. Man beginnt mit der unendlich langen Liste aller natürlichen Zahlen größer als 1. In ihr ist die kleinste Zahl, die 2, eine Primzahl. Man entfernt sie und alle ihre Vielfachen aus der Liste. Die kleinste Zahl der Restliste, die 3, ist die nächste Primzahl. Man entfernt sie und alle ihre Vielfachen aus der Liste usw.

Natürlich ist dieses theoretische Verfahren nicht praktikabel, um schnell eine beliebig lange Liste von Primzahlen zu erzeugen. Es ist bis heute auch keine Formel bekannt, die es gestattet, schnell beliebig große Primzahlen zu berechnen, oder aus einer gegebenen Primzahl eine noch größere Primzahl herzustellen.

Daher gibt es beim aktuellen Stand der Forschung immer eine zur Zeit größte bekannte Primzahl und der augenblickliche Rekord steht bei

21398269-1.

Es ist nun keineswegs so, daß man alle Primzahl unterhalb dieser sehr großen Zahl kennt, wie das beim Siebverfahren des Eratosthenes der Fall wäre. Wie kommt man also ausgerechnet auf diese Zahl?

Mersennesche Primzahlen

In der Antike und bis ins Mittelalter glaubte man, daß für jede Primzahl p die Zahl 2p-1 wieder eine Primzahl ist. Dabei ist klar, daß 2k-1 für eine zusammengesetzte Zahl k=mn wegen

2k-1=(2m-1)(2(n-1)m+2(n-2)m +...+2m+1)

keine Primzahl sein kann. So wurde etwa 1456 von einem unbekannten Mathematiker die Primzahleigenschaft von 213-1 bewiesen. Daher war man erstaunt, als 1536 Hudalricus Regius die Zerlegung von 211-1=2047=23*89 fand. Im Jahre 1603 hatte Pietro Cataldi bewiesen, daß auch 217-1 und 219-1 Primzahlen sind, und dann behauptet, daß dies auch für die Exponenten p=23, 29, 31 und 37 zuträfe. Pierre Fermat zeigte 1640 jedoch, daß diese Behauptung für p=23 und 37 falsch ist und Leonhard Euler zeigte 1738 dasselbe für p=29, konnte allerdings 1750 wirklich beweisen, daß 231-1 eine Primzahl ist.

Im Jahre 1644 behauptete nun der französische Mönch Marin Mersenne im Vorwort seiner Cogitata Physica-Mathematica, daß für alle Primzahlen bis 257 nur die Fälle

p=2,3,5,7,13,17,19,31,67,127, 257

eine Primzahl 2p-1 lieferten.

Wenn man etwa die Größe der Primzahl (1876 von Lucas bewiesen)

2127-1=170141183460469231731687303715884105727

bedenkt, so dürfte klar sein, daß Mersenne zu seiner Zeit unmöglich für alle Primzahlen p bis 257 die Primzahleigenschaft von 2p-1 wirklich überprüft haben kann. So irrte er auch in den Fällen p=67 und 257. Außerdem bewies Pervouchine 1883, daß Mersenne den Fall p=61 übersehen hatte und Powers zeigte dasselbe 1911 für p=89 und 1914 für p=107. Trotzdem nennt man die Zahlen Mn=2n-1 heute Mersennesche Zahlen und insbesondere Mersennesche Primzahlen, wenn sie tatsächlich prim sind. Erst 1947 hatte man für alle Primzahlen p bis 257 wirklich überprüft, welche von ihnen Mersennsche Primzahlen liefern. Es sind dies

p=2,3,5,7,13,17,19,31,61, 89,107,127.

Warum ausgerechnet Mersennesche Primzahlen?

Daß bei der Rekordjagd nach immer größeren Primzahlen mittels Computer die Mersenneschen Primzahlen eine so bedeutende Rolle spielen, hat verschiedene Gründe. Zum einen ist wegen der Binärdarstellung 111....111 (p Einsen) der Zahl 2p-1 dies gerade die größte Zahl, die man in einem Computer mit dieser Stellenzahl darstellen kann, zum anderen kennt man aber auch einige theoretische Aussagen über Mersennesche Primzahlen. Dies kann den Test auf die Primzahleigenschaft gegenüber beliebigen natürlichen Zahlen erheblich abkürzen. So gilt etwa der folgende Satz von Lucas, auf dem der sogenannte Lucas-Lehmer-Test beruht.

Satz: Für eine ungerade Primzahl p ist Mp genau dann eine Primzahl, wenn sie die Lucas-Zahl Lp-1 teilt.

Dabei sind die Lucas-Zahlen rekursiv durch L1=4 und Ln+1=Ln2-2 definiert.

Welche Mersenneschen Primzahlen sind zur Zeit bekannt?

In der folgenden Tabelle sind in fortlaufender Numerierung die Mersenneschen Primzahlen Mp durch ihre erzeugende Primzahl p angegeben. Zusätzlich findet man weitere Informationen über Mp.

Für die letzten vier Einträge ist zur Zeit noch unbekannt, ob zwischen ihnen nicht noch weitere Mersenneschen Primzahlen liegen. Es läuft ein über das Internet verbreiteter Test der Primzahlen p in den verbleibenden Lücken, an dem sich jeder Interessierte mit entsprechender Computerkapazität beteiligen kann. Eine Anlaufadresse ist

http://www.utm.edu/research/primes/mersenne.shtml

Nr. p Dezimalstellen von Mp Entdeckungsjahr Entdecker
1 2 1 - -
2 3 1 - -
3 5 2 - -
4 7 3 - -
5 13 4 1456 unbekannt
6 17 6 1588 Cataldi
7 19 6 1588 Cataldi
8 31 10 1772 Euler
9 61 19 1883 Pervushin
10 89 27 1911 Powers
11 107 33 1914 Powers
12 127 39 1876 Lucas
13 521 157 1952 Lehmer & Robinson
14 607 183 1952 Lehmer & Robinson
15 1279 386 1952 Lehmer & Robinson
16 2203 664 1952 Lehmer & Robinson
17 2281 687 1952 Lehmer & Robinson
18 3217 969 1957 Riesel
19 4253 1281 1961 Hurwitz & Selfridge
20 4423 1332 1961 Hurwitz & Selfridge
21 9689 2917 1963 Gillies
22 9941 2993 1963 Gillies
23 11213 3376 1963 Gillies
24 19937 6002 1971 Tuckerman
25 21701 6533 1978 Noll & Nickel
26 23209 6987 1979 Noll
27 44497 13395 1979 Nelson & Slowinski
28 86243 25962 1982 Slowinski
29 110503 33265 1988 Colquitt & Welsh
30 132049 39751 1983 Slowinski
31 216091 65050 1985 Slowinski
32 756839 227832 1992 Slowinski & Gage
? 859433 258716 1994 Slowinski & Gage
? 1257787 378632 1996 Slowinski & Gage
? 1398269 420921 1996 Armengaud et al.

Udo Hebisch
Inst. f. Theor. Math.
TU Bergakademie Freiberg