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 $p$ ₁, p₂, ... p_n, dann ist die Zahl $m=p$ ₁*p₂* ... *p_n+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

2^43'112'609-1.

Es ist nun keineswegs so, daß man alle Primzahlen 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 $2$ ^p-1 wieder eine Primzahl ist. Dabei ist klar, daß $2$ ^k-1 für eine zusammengesetzte Zahl k=mn wegen

2

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

keine Primzahl sein kann. So wurde etwa 1456 von einem unbekannten Mathematiker die Primzahleigenschaft von $2$ ¹³-1 bewiesen. Daher war man erstaunt, als 1536 Hudalricus Regius die Zerlegung von $2$ ¹¹-1=2047=23*89 fand. Im Jahre 1603 hatte Pietro Cataldi bewiesen, daß auch $2$ ¹⁷-1 und $2$ ¹⁹-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ß $2$ ³¹-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 $2$ ^p-1 lieferten.

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

2

¹²⁷-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 $2$ ^p-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 $M$ _n=2ⁿ-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

2

^p-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 $M$ _p genau dann eine Primzahl, wenn sie die Lucas-Zahl $L$ _p-1 teilt.

Dabei sind die Lucas-Zahlen rekursiv durch $L$ ₁=4 und $L$ _n+1=L_n²-2 definiert.

Welche Mersenneschen Primzahlen sind zur Zeit bekannt?

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

Ab dem 40. Eintrag ist zur Zeit noch unbekannt, ob zwischen ihnen nicht noch weitere Mersennesche 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 $M$ _p 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
33 859433 258716 1994 Slowinski & Gage
34 1257787 378632 1996 Slowinski & Gage
35 1398269 420921 1996 Armengaud et al.
36 2976221 895932 1997 Spence et al.
37 3021377 909526 1998 Clarkson et al.
38 6972593 2098960 1999 Hajratwala et al.
39 13466917 4053946 2001 M.Cameron et al.
40? 20996011 6320430 2003 Michael Shafer (GIMPS)

41? 24036583 7235733 2004 Findley,Woltman, Korowski & GIMPS

42? 25964951 7816230 2005 Nowak,Woltman, Korowski & GIMPS

43? 30402457 9152052 2005 C. Cooper, S. Boone & GIMPS

44? 32582657 9808358 2006 C. Cooper, S. Boone & GIMPS
45? 37156667 11185272 2008 Elvenich, Woltman, Kurowski & GIMPS
46? 42643801 12837064 2009 Strindmo, Woltman, Kurowski & GIMPS
47? 43112609 12978189 2008 Smith, Woltman, Kurowski & GIMPS

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

aktualisiert zuletzt am 18.9.2009 durch Hansruedi Schneider, KSBG St. Gallen

Nr.	p	Dezimalstellen von $M$ _p	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
33	859433	258716	1994	Slowinski & Gage
34	1257787	378632	1996	Slowinski & Gage
35	1398269	420921	1996	Armengaud et al.
36	2976221	895932	1997	Spence et al.
37	3021377	909526	1998	Clarkson et al.
38	6972593	2098960	1999	Hajratwala et al.
39	13466917	4053946	2001	M.Cameron et al.
40?	20996011	6320430	2003	Michael Shafer (GIMPS)
41?	24036583	7235733	2004	Findley,Woltman, Korowski & GIMPS
42?	25964951	7816230	2005	Nowak,Woltman, Korowski & GIMPS
43?	30402457	9152052	2005	C. Cooper, S. Boone & GIMPS
44?	32582657	9808358	2006	C. Cooper, S. Boone & GIMPS
45?	37156667	11185272	2008	Elvenich, Woltman, Kurowski & GIMPS
46?	42643801	12837064	2009	Strindmo, Woltman, Kurowski & GIMPS
47?	43112609	12978189	2008	Smith, Woltman, Kurowski & GIMPS