Große Internet-Suche nach Mersenne-Primzahlen (GIMPS)

Einleitung

Wie funktioniert GIMPS?

Historie des GIMPS-Projekts

bisher gefundene Mersenne-Primzahlen

Links zum Mitmachen

 

Primzahlen? Wie war das doch gleich in der Schule? Ach ja, Primzahlen sind diejenigen Zahlen, die sich nur durch die Zahl 1 und durch sich selbst ohne Rest teilen lassen. Die Zahl 3 ist eine Primzahl und auch die 5, aber nicht die Zahl 6, denn die ist ja durch 2 und durch 3 teilbar. Und dann gibt es noch eine besondere Gruppe von Primzahlen, die nach einem französischen Mönch aus dem Mittelalter (1588-1648) sogenannten Mersenne-Primzahlen.

Mersenne-Primzahlen sind Primzahlen, die sich so darstellen lassen: 2x2x2x2x2x2x2......x2-1. Leider gilt der Umkehrschluß aber nicht: nicht alle Zahlen, die man so schreiben kann, sind Primzahlen. Beispielsweise die Zahl 15. Kann man auch schreiben als 2x2x2x2-1. Lässt sich aber durch 3 und durch 5 teilen und scheidet daher als Primzahl aus. Auch 63 ist keine solche Primzahl. Man kann 63 zwar darstellen als 2x2x2x2x2x2-1, es ist aber durch 3 und durch 7 teilbar!

Aber zum Beispiel
3 (=2x2-1) und 7 (=2x2x2-1) sowie 31 (=2x2x2x2x2-1) sind Mersenne-Primzahlen. Insgesamt kennt man erst 49 Mersenne-Primzahlen, bei der größten dieser Zahlen, wird die Zahl 2 insgesamt 74.207.281 mal mit sich selbst multipliziert und vom Ergebnis wird 1 abgezogen. Das Resultat ist eine Zahl mit 22.338.618 Ziffern! Die nur durch sich selbst und die Zahl 1 teilbar ist!

Um noch größere Mersenne-Primzahlen zu finden, braucht man entweder einige Supercomputer, oder noch sehr viel mehr "gewöhnliche" PC´s, Laptops, Mac´s und andere Rechner, die zu Hause oder im Büro Verwendung finden. Denn die sind auch durch den schnellsten Briefeschreiber nur zu einem winzigen Bruchteil ausgelastet. Und den Rest der Zeit warten sie auf den nächsten Tastendruck oder den nächsten Mausklick.

Deswegen gibt es seit Januar 1996 im Internet ein Projekt, an dem jeder Computerbesitzer teilnehmen kann: die Große Internet-Suche nach Mersenne-Primzahlen oder auch Great Internet Mersenne Prime Search, abgekürzt GIMPS. Dieses Projekt nutzt die Leerlaufzeit, die jeder Computer während des Betriebs aufweist, um eine noch größere Mersenne-Primzahl zu finden. Es soll allerdings auch Zeitgenossen geben, die ihren Computer tage- und nächtelang laufen lassen, nur um an diesem Projekt teilzunehmen!

Im Rahmen dieser weltweiten Suche wird derzeit mit zehntausenden Computern aller Art nach der
50. Mersenne-Primzahl gesucht. Und der Entdecker wird auf lange Zeit in den Geschichtsbüchern der Mathematik nachzulesen sein. Allerdings muß er sich den Ruhm mit allen anderen GIMPS-Teilnehmern und Teams teilen. Denn der Einzelne würde bei der Suche nach der 50. Mersenne-Primzahl alt und grau werden; nur die Vielzahl der Teilnehmer sichert einen Treffer in überschaubarer Zeit. Die Gesamtrechenleistung liegt derzeit (Januar 2016) bei ungefähr 402.000 Milliarden Rechenoperationen in jeder Sekunde!

Die größte derzeit bekannte Primzahl wurde von Dr. Curtis Cooper in den USA am 7. Januar 2016 entdeckt. Wie alle anderen Teilnehmer an dem GIMPS-Projekt musste er auch nicht zwingend etwas von der zugrunde liegenden Mathematik oder dem verwendeten Rechenprogramm verstehen. Er hat „einfach“ das kostenlos im WWW erhältliche Programm PRIME95 oder eine vergleichbare freie Software eingesetzt und damit herausgefunden, dass

274.207.281-1 die 49. bekannte Mersenne-Primzahl ist!

Mersenne-Primzahlen und vollkommene Zahlen

Es ist übrigens so, dass mit der Entdeckung einer neuen Mersenne-Primzahl auch eine neue vollkommene Zahl entdeckt ist. Man spricht von einer vollkommenen Zahl, wenn eine Zahl sich als Summe ihrer Teiler darstellen lässt. Die kleinste vollkommene Zahl ist 6, denn 6 ist die Summe der Zahlen 1, 2 und 3, die alle Teiler von 6 sind. Die zweitkleinste vollkommene Zahl ist 28; die Summe ihrer Teiler 1, 2, 4, 7 und 14 ergibt 28. Wenn eine neue Mersenne-Primzahl der Form 2p-1 entdeckt wird, ergibt sich "automatisch" eine neue vollkommene Zahl nach der Formel z = 2p-1 x 2p-1; z ist hier die vollkommene Zahl. Bereits im Altertum waren die vollkommenen Zahlen bekannt und besonders begehrt, da sie sehr selten auftreten und eben etwas besonderes darstellen. Übrigens ist bis heute die Frage nicht geklärt, ob es auch ungerade vollkommene Zahlen geben kann. Man weiss zumindest, dass eine solche Zahl mehr als etwa 300 Ziffern haben müsste. Wer den Nachweis führt, dass es eine ungerade vollkommene Zahl gibt (oder auch nicht gibt), hat ebenfalls die Möglichkeit, schlagartig in der Welt der Mathematik bekannt zu werden.


Wie funktioniert GIMPS?

Bei GIMPS werden nur Zahlen der Form 2p-1 überprüft, bei denen die Zahl p selbst eine Primzahl ist. Nur diese Zahlen sind Kandidaten für eine Mersenne-Primzahl. Einen Beweis dafür können Sie an anderer Stelle im Internet abrufen. Beispielsweise hier.

Für die Teilnahme an GIMPS ist das Nachvollziehen des Beweises natürlich nicht notwendig. Die Überprüfung läuft in drei Schritten ab:

Factoring

Bei diesem ersten Schritt werden in einem eingegrenzten Bereich vorab Teiler gesucht. Wenn ein Teiler gefunden wird, die Zahl also keine Primzahl sein kann, ist sie quasi aus dem Rennen. Wenn hingegen kein Teiler gefunden wird, dann geht es weiter mit dem nächsten Schritt. Beim Factoring können auch "langsame" Computer problemlos teilnehmen.

Lucas-Lehmer-Test

Dieses Verfahren prüft eine Zahl vollständig auf ihre Eigenschaft als Primzahl. Nur ganz selten wird tatsächlich eine Primzahl entdeckt, aber genau das ist der eigentliche Sinn von GIMPS. Hier sollte der Computer schon etwas schneller sein.

Sie können ganz schnell selbst herausfinden, wie lange Ihr Rechner für einen bestimmten Lucas-Lehmer-Test brauchen wird: einfach diese Seite aufrufen, die individuellen Daten Ihres Rechners (CPU, Takfrequenz, Betriebsstunden pro Tag) eintragen und Sie erhalten sofort die Antwort, wie lange die Berechnung dauern wird.

Seit der Programm-Version 20.4 ist beim Lucas-Lehmer-Test noch eine weitere Factoring-Stufe vorgeschaltet, das sogenannte P-1-Factoring. Dieses bietet gegenüber dem oben beschriebenen Factoring erweiterte Möglichkeiten, in kurzer Zeit doch noch einen Primfaktor der Zahl zu finden und sich damit das wochenlange Testen im Rahmen des Lucas-Lehmer-Tests (sowie des Double-Checkings) zu ersparen. Durch diesen Schritt wird voraussichtlich die Gesamtleistung von GIMPS weiter ansteigen.

Wie funktioniert dieser Lucas-Lehmer-Test?

Nun, es werden eigentlich nur Grundrechenarten verwendet und das Verfahren ist schon als genial zu bezeichnen. Aber immerhin haben wir es mit Zahlen von mehreren Millionen Stellen Umfang zu tun und da hört es dann auf, einfach zu sein. Um zu bestimmen, ob eine Mersenne-Zahl auch eine Primzahl ist, beginnt man mit dem Ausgangswert 4. (Es gibt auch andere Werte, für die das funktioniert, aber bleiben wir mal bei der 4.)

Dieser Wert wird mit sich selbst multipliziert und es wird 2 abgezogen. Man erhält 14. Und teilt 14 durch die zu überprüfende Mersennezahl. Da bleibt ein Rest. Dieser wird erneut quadriert und es wird wieder 2 abgezogen. Dieses Verfahren ist dann insgesamt p-2 mal zu wiederholen, wobei p ja der Exponent der Mersennezahl ist. Vielleicht lässt es sich doch besser an einem Beispiel zeigen:

25-1=31. Der Exponent (p) ist 5, wir müssen das Verfahren also bis zum dritten (p-2) Schritt laufen lassen:

1. Schritt: (4*4-2)/31=0 Rest 14

2. Schritt: (14*14-2)/31=6 Rest 8

3. Schritt: (8*8-2)/31=2 Rest 0

Und wenn nach p-2 Durchläufen ein Rest 0 übrig bleibt, dann ist die Zahl, in dem Fall 31, tatsächlich eine Primzahl!

Der Lucas-Lehmer-Test erlaubt also, Zahlen von Millionen Ziffern Länge in überschaubarer Zeit (Wochen/Monate) auf ihre Eigenschaft als Primzahl zu überprüfen. Durch bloßes Suchen von Teilern wäre das nicht möglich, da das viel zu lange dauern würde. Auch wenn man bekanntermaßen nur bis zur Quadratwurzel der zu überprüfenden Zahl suchen muss! Bis zum 30. August 2001 kannte man z. B. keinen einzigen Teiler der Zahl 2727-1, von der natürlich dank Lucas-Lehmer-Test bekannt war, dass es sich nicht um eine Primzahl handelt, sie also Teiler haben muss. Man weiss aber andererseits, dass die sehr viel größere Zahl 274.207.281-1 eine Primzahl ist. Das hatte im erstgenannten Fall einfach damit zu tun, dass es keine geeigneten schnellen Verfahren gibt, die Zahlen von mehr als ca. 200 Ziffern Länge in ihre Primfaktoren zerlegen können. Auch die immer schneller werdenden Computer konnten hieran bisher nichts ändern. Wenn Sie also die Mathematik auf dem Gebiet der Zahlentheorie voranbringen wollen, können Sie sich ein Verfahren überlegen, das riesige Zahlen im Handumdrehen in ihre Primfaktoren zerlegt. :-))

Auf der anderen Seite ermöglicht der Lucas-Lehmer-Test wie gesagt ausschließlich eine Ja-/Nein-Aussage über die Eigenschaft einer Zahl als Primzahl. Aber auch nicht mehr, er liefert also bei den Nichtprimzahlen keine Teiler. Da sich dieser Test so hervorragend auch zur Untersuchung sehr großer Zahlen eignet, sind die größten bekannten Primzahlen samt und sonders Mersenne-Primzahlen.

Double-Checking

Da auch Computer Fehler machen können, wird jede Zahl einer zweiten vollständigen Prüfung unterzogen. Das ist auch ein Lucas-Lehmer-Test, der durchaus ergeben kann, dass eine Zahl eine Primzahl ist, auch wenn bei der ersten Überprüfung das Gegenteil herausgekommen sein sollte. Etwa 1% aller Lucas-Lehmer-Tests liefern nämlich ein falsches Ergebnis. Ein solcher Test ist eine starke Belastung für die CPU, insbesondere die Floating Point Unit (FPU), und kann fehlerhafte Ergebnisse produzieren. Auch und gerade dann, wenn der Lucas-Lehmer-Test ergeben hat, dass eine Primzahl vorliegt, wird ein zweiter Durchgang fällig, um die notwendige Sicherheit zu erhalten. Die Anforderungen an den Rechner sind dieselben wie beim Lucas-Lehmer-Test, allerdings sind die zu überprüfenden Zahlen durchweg kleiner.

Verteilen der Aufgaben / Übermittlung der Ergebnisse

Die Verteilung der Aufgaben und die Sammlung der Ergebnisse übernimmt der PrimeNet-Server in den USA. Es gibt sowohl die Möglichkeit, neue Aufgaben und Ergebnisse automatisch übermitteln zu lassen - immer dann, wenn Sie ohnehin gerade im Internet sind - als auch die Option, manuelle Formulare zu benutzen, um neue Aufgaben abzuholen und Ergebnisse zu übermitteln.


Historie des GIMPS-Projekts

Januar 1996

Projekt gestartet

13. November 1996

Joel Armengaud findet die 35. Mersenne-Primzahl: 21.398.269-1

24. August 1997

Gordon Spence weist die 36. Mersenne-Primzahl nach: 22.976.221-1

27. Januar 1998

Roland Clarkson entdeckt die 37. Mersenne-Primzahl: 23.021.377-1

Mai 1999

mehr als 20.000 Rechner beteiligt

1. Juni 1999

Nayan Hajratwala spürt die 38. Mersenne-Primzahl auf: 26.972.593-1

Februar 2000

GIMPS erreicht 1000 Milliarden Rechenoperationen/Sekunde

September 2000

30.000 Rechner nehmen an GIMPS teil

Januar 2001

35.000 Rechner sind an der Suche nach der 39. Mersenne-Primzahl beteiligt; GIMPS besteht als Projekt nun seit 5 Jahren; die Rechenleistung liegt aktuell bei ca. 1500 Milliarden Operationen in jeder Sekunde; insgesamt wurden 4 neue Mersenne-Primzahlen entdeckt

ca. März 2001

Je mehr als 10.000 Rechner mit Pentium III- und Athlon-Prozessoren sind an der Suche beteiligt

April 2001

GIMPS erreicht die Leistung von 30 Supercomputern Cray T 932

September 2001

Version 21.4 des PRIME95-Programms ist "offiziell" verfügbar. P4-Rechner sind damit 3x so schnell wie mit Version 20; Athlons, PIII und Celerons der 2. Generation verbuchen einen Geschwindigkeitssprung von bis zu 25%. Die Rechnerzahl insgesamt ist auf unter 32.000 gefallen. Davon sind etwa 9.000 mit einem Athlon- und weitere 9.000 mit einem Pentium III-Prozessor ausgestattet. Trotz der seit März 2001 zurückgegangenen Zahl an teilnehmenden Rechnern ist die Gesamtrechenleistung nicht zuletzt dank der neuen Programmversion gestiegen! Außerdem wurden offenbar ältere Rechner durch leistungsstärkere Systeme ersetzt.

Oktober 2001

GIMPS überschreitet die Marke von 2 Billionen Rechenoperationen pro Sekunde (2 Teraflops)

14. November 2001

GIMPS ist zum 5. Mal in knapp 6 Jahren erfolgreich: 213.466.917-1 ist die 39. bekannte Mersenne-Primzahl! Entdeckt wurde diese neue Rekordprimzahl auf dem Rechner von Michael Cameron aus Kanada.

Januar 2002

GIMPS erreicht die Marke von 3 Billionen Operationen pro Sekunde! (3 Teraflops)

Januar 2002

Mehr als 40.000 Rechner nehmen an der Suche nach der 40. Mersenne-Primzahl teil!

Juni 2002

GIMPS erreicht die Marke von 4 Billionen Operationen pro Sekunde! (4 Teraflops)

Oktober/November 2002

Nun sind es 5 Billionen Operationen pro Sekunde.... die aktuelle Programmversion ist 22.12.

Februar 2003

GIMPS sucht mit 6 Billionen Operationen je Sekunde nach der 40. Mersenne-Primzahl und beweist durch Double-Checking, dass M6972593 die 38. Mersenne-Primzahl ist.

Mai 2003

Nach einem zwischenzeitlichen Schwund sind wieder 40.000 und mehr Rechner an der Suche beteiligt... 7 Teraflops sind erreicht.....

Juli 2003

Version 23.5 beschleunigt ältere Prozessoren um bis zu 8%.....

Oktober 2003

GIMPS hat stabil die 8 TFlops-Marke überschritten. Aktuell ist Version 23.7.

17. November 2003

Und wieder schlägt GIMPS zu: die 40. Mersenne-Primzahl heisst 220.996.011-1; gefunden auf dem Rechner von Michael Shafer.

Dezember 2003

Die Teilnehmerzahlen explodieren und die Rechenleistung liegt zwischen 9 und 10 TFlops....

Januar 2004

GIMPS überschreitet 60.000 teilnehmende Rechner, 11 und 12 TFlops sowie die Marke von 1.000 CPU-Jahren (P90) pro Tag. Letzteres bedeutet, dass ein Pentium-90-Rechner 1.000 Jahre laufen müsste, damit er dieselbe Leistung vollbringt wie das GIMPS-Netzwerk an einem einzigen Tag....

15. Mai 2004

Nach nur einem halben Jahr der nächste Erfolg: 224.036.583-1 ist ebenfalls eine Primzahl; der 7. Treffer für GIMPS und die 41. Mersenne-Primzahl überhaupt!

18. Februar 2005

GIMPS hat es wieder gepackt: 225.964.951-1 ist der neue Rekordhalter, gefunden auf dem Rechner von Dr. Martin Nowak.

15.Dezember 2005

Drs. Boone und Cooper von der Central Missouri State University setzen die Erfolgsgeschichte von GIMPS fort und finden heraus, dass 230.402.457-1 ebenfalls eine Primzahl ist.

22. Januar 2006

GIMPS feiert sein 10-jähriges Bestehen und ist damit wahrscheinlich das älteste "Distributed computing"-Projekt der Welt! Und natürlich auch das erfolgreichste derartige Projekt....

4. September 2006

Ab sofort ist der neue Rekordhalter 232.582.657-1!!!

23. August 2008

Und wieder war es soweit: 243.112.609-1 ist prim, festgestellt durch GIMPS! Dies ist nun die größte bekannte Primzahl!

6. September 2008

Doppelschlag nach nur 2 Wochen: GIMPS ermittelt 237.156.667 -1 als weitere Mersennezahl mit Primzahleigenschaft!!!

12. April 2009

Nahezu unbemerkt und erst 2 Monate später bestätigt: der Treffer von Odd Magnar Strindmo aus Norwegen: 242.643.801-1

25. Januar 2013

Dr. Cooper landet den dritten Erfolg! Es ist 257.885.161-1!

7. Januar 2016

Dr. Cooper schon wieder erfolgreich! Diesmal ist es 274.207.281-1! GIMPS rechnet nun seit 20 Jahren!


bisher gefundene Mersenne-Primzahlen

Nr.

Exponent p

Datum/Jahr

Ziffern

Entdecker

<49>

74.207.281

07.01.2016

22.338.618

GIMPS (Dr. Cooper)

<48>

57.885.161

25.01.2013

17.425.170

GIMPS (Dr. Cooper)

<47>

43.112.609

23.08.2008

12.978.189

GIMPS (Edson Smith)

<46>

42.643.801

12.04.2009

12.837.064

GIMPS (Odd Magnar Strindmo)

45

37.156.667

06.09.2008

11.185.272

GIMPS (Hans-Michael Elvenich)

44

32.582.657

04.09.2006

9.808.358

GIMPS (Drs. Boone und Cooper)

43

30.402.457

15.12.2005

9.152.052

GIMPS (Drs. Boone und Cooper)

42

25.964.951

18.02.2005

7.816.230

GIMPS (Dr. Martin Nowak)

41

24.036.583

15.05.2004

7.235.733

GIMPS (Josh Findley)

40

20.996.011

17.11.2003

6.320.430

GIMPS (Michael Shafer)

39

13.466.917

14.11.2001

4.053.946

GIMPS (Michael Cameron)

38

6.972.593

01.06.1999

2.098.960

GIMPS (Nayan Hajratwala)

37

3.021.377

27.01.1998

909.526

GIMPS (Roland Clarkson)

36

2.976.221

24.08.1997

895.932

GIMPS (Gordon Spence)

35

1.398.269

13.11.1996

420.921

GIMPS (Joel Armengaud)

34

1.257.787

03.09.1996

378.632

Slowinski & Gage

33

859.433

01.02.1994

258.716

Slowinski & Gage

32

756.839

01.04.1992

227.832

Slowinski & Gage

31

216.091

01.09.1985

65.050

Slowinski

30

132.049

19.09.1983

39.751

Slowinski

29

110.503

28.01.1988

33.265

Colquitt & Welsh

28

86.243

25.09.1982

25.962

Slowinski

27

44.497

08.04.1979

13.395

Nelson & Slowinski

26

23.209

09.02.1979

6.987

Noll

25

21.701

30.10.1978

6.533

Noll & Nickel

24

19.937

04.03.1971

6.002

Tuckerman

23

11.213

02.06.1963

3.376

Gillies

22

9.941

16.05.1963

2.993

Gillies

21

9.689

11.05.1963

2.917

Gillies

20

4.423

03.11.1961

1.332

Hurwitz

19

4.253

03.11.1961

1.281

Hurwitz

18

3.217

08.09.1957

969

Riesel

17

2.281

09.10.1952

687

Robinson

16

2.203

07.10.1952

664

Robinson

15

1.279

26.06.1952

386

Robinson

14

607

30.01.1952

183

Robinson

13

521

30.01.1952

157

Robinson

12

127

1876

39

Lucas

11

107

1914

33

Powers

10

89

1911

27

Powers

9

61

1883

19

Pervushin

8

31

1772

10

Euler

7

19

1588

6

Cataldi

6

17

1588

6

Cataldi

5

13

1456

4

 

4

7

275 v. Chr.?

3

 

3

5

275 v. Chr.?

2

 

2

3

500 v. Chr.?

1

 

1

2

500 v. Chr.?

1

 

 

Anmerkung: Der Bereich oberhalb der 45. Zahl wurde noch nicht vollständig durch Double-Checking überprüft, sodass nicht mit Sicherheit gesagt werden kann, dass die 46. Mersenne-Primzahl auch die 46. Zahl dieser Art ist. Es besteht noch die Möglichkeit, dass kleinere Mersenne-Primzahlen als die Zahl Nr. 46 gefunden werden. Bitte beachten Sie, dass die 29. Mersenne-Primzahl erst einige Jahre nach der 30. und sogar auch nach der 31. Mersenne-Primzahl in der Tabelle gefunden wurde. Die 12. Zahl der Tabelle wurde sieben Jahre vor der 9. Zahl gefunden.


Wollen auch Sie bei der Suche nach der 50. Mersenne-Primzahl mithelfen?

*** Sie brauchen dafür nur einen Computer (PC, Mac), der nicht gerade von vorgestern ist, und schon geht es los! ***

Homepage des GIMPS-Projekts

Übersicht / eigener Account / Aufgaben abholen / Ergebnisse einsenden

Status der Suche im Überblick (Meilensteine)

Software zum Mitmachen für viele Systeme zum Download

FTP-Server (Spiegel) mit aktuellen Downloads

Forum

***

Mail an mich (Fragen, Anregungen, Kritik)

***

Stand der Seite: 23.11.2016