Great Internet Mersenne Prime Search

Logo

Die Great Internet Mersenne Prime Search (GIMPS) ist ein gemeinschaftliches Projekt zur computergestützten Suche nach Mersenne-Primzahlen. Das Projekt wurde von George Woltman gegründet, der auch die Software Prime95 und MPrime für das Projekt schrieb. Scott Kurowski programmierte den Internet PrimeNet^[1] -Server. GIMPS ist als Mersenne Research, Inc. eingetragen. Es war der erste umfangreiche Einsatz von verteiltem Rechnen über das Internet für Forschungszwecke, bei dem Computernutzer ihre Rechenzeit freiwillig zur Verfügung stellten (Volunteer-Computing).

Das GIMPS-Forschungsprojekt

GIMPS bietet weltweit die Beteiligung an einem Volunteer-Computing-Projekt an, um Mersenne-Primzahlen zu finden. Die erforderliche Software, die George Woltman ab 1996 programmierte, kann von der GIMPS-Download-Webseite^[2] heruntergeladen werden. Als Prime95 und MPrime ist diese Software zum Installieren auf verschiedenen Intel bzw. AMD Mikroprozessor-basierten Betriebssystemen verfügbar, unter anderem für Windows 64-bit und 32-bit, macOS, Linux 64-bit und 32-bit, FreeBSD und PC-BSD 64-bit und 32-bit. Für andere Computerplattformen stehen die Programme Mlucas^[3] und Glucas^[4] zur Verfügung. Nach der Installation der jeweiligen Prime95-Softwareversion auf einem Computer kommuniziert diese im laufenden Betrieb mit dem Internet PrimeNet Server^[1] von Scott Kurowski, um u. a. (Zwischen-)Ergebnisse zu registrieren, eliminierte Mersenne-Primzahlkandidaten zu speichern und GIMPS Nutzerdaten zu verwalten. Der GIMPS PrimeNet Server ist zusammen mit den lose gekoppelten Computern, die Prime95 oder MPrime ausführen, ein Grid-Computing-Netzwerk für Verteiltes Rechnen, bei dem ein virtueller Supercomputer für die rechenintensive wissenschaftlich-mathematische Suche nach Mersenne-Primzahlen entsteht.

Der GIMPS-Supercomputer erzielte am 6. April 2000 den Preis der Electronic Frontier Foundation (EFF) von 50.000 US$ für das erstmalige Auffinden einer Primzahl mit mehr als einer Million Dezimalziffern. Es handelt sich um die 38. Mersenne-Primzahl M_6.972.593,^[5] die 2.098.960 Stellen hat und am 1. Juni 1999 mit einem 350 MHz Pentium II IBM Aptiva PC gefunden wurde. Der Preis ging zu Teilen an GIMPS und Nayan Hajratwala aus Plymouth, Michigan.^[6] Edson Smith^[7] fand die 47.^[8] bekannte Mersenne-Primzahl M_43.112.609, welche am 12. April 2009 vom GIMPS-Projekt registriert und am 12. Juni 2009 veröffentlicht wurde. Edson Smith, George Woltman, Scott Kurowski, u. a. erhielten den Preis der EFF für das erstmalige Auffinden einer Primzahl mit mehr als zehn Millionen Ziffern von 100.000 US$,^[9] er ging am 14. Oktober 2009 zu Teilen an GIMPS und das Mathematikdepartment der University of California in Los Angeles (UCLA).

Mit 150.000 US$ für das Auffinden der ersten Primzahl mit mehr als 100 Millionen Dezimalziffern (100.000.000) und 250.000 US$ für das erste Finden einer Primzahl mit mehr als 1 Milliarde Dezimalziffern (1.000.000.000) sind zwei weitere Preise, die sogenannten Cooperative Computing Awards der EFF,^[10] ausgeschrieben. Der GIMPS-Supercomputer beteiligt sich daran,^[11] in der Prime95- bzw. der MPrime-Software und in der Verwaltung des eigenen Kontos auf dem PrimeNet-Server, zur Steuerung der Prime95- bzw. der MPrime-Software, kann die Suche nach 100-millionenzifferigen Mersenne-Primzahlen eingestellt werden.

Status

Anfang Februar 2013 hat GIMPS einen mittleren Durchsatz von ca. 130,546 TFLOP/s (Billionen Rechenoperationen pro Sekunde) geleistet.^[12] Im März 2012 hatte GIMPS einen mittleren Durchsatz von ca. 86,107 TFLOP/s,^[13] was GIMPS theoretisch den Platz 153 unter den leistungsstärksten Computern der Welt einbrachte.^[14] Im Oktober 2010 leistete GIMPS-PrimeNet rund 50 TFLOP/s, Mitte 2008 waren es ca. 30 TFLOP/s, Mitte 2006 ca. 20 TFLOP/s und zu Anfang 2004 ca. 14 TFLOP/s. Im Januar 2017 lag die Leistung bereits bei rund 367 PFLOP/s und damit theoretisch auf Rang 468 der Weltrangliste.^[15]

Geschichte

Das GIMPS-Projekt begann im Januar 1996 mit einem Programm, das auf i386-Computern lief.^[16][17] Der erste getestete Exponent damals war M_859.433.^[18] Der Name für das Projekt wurde von Luther Welsh gefunden, einer der ersten Teilnehmer und der Entdecker der 29. Mersenne-Primzahl.^[19] Innerhalb weniger Monate hatten sich 1996 mehrere Dutzend Personen angeschlossen, über Tausend am Ende des ersten Jahres.^[17][20] Joel Armengaud, ein Teilnehmer, entdeckte die Primalität von M_1.398.269 am 13. November 1996.^[21]

Gefundene Primzahlen

Siehe: Mersenne-Primzahl

Bis dato (Oktober 2024) hat das Projekt insgesamt 18 Mersenne-Primzahlen gefunden. Aktuell ist die größte Primzahl 2^136,279,841 − 1 (oder kurz M_136279841). Sie wurde am 12. Oktober 2024 von Luke Durant entdeckt.^[22][23]

Mersenne-Primzahlen sind Potenzen von 2 minus 1, etwa 2³-1=7, während etwa die Mersenne-Zahl 2⁴-1=15 nicht prim ist. Sie werden mit M_q bezeichnet, wobei q der Exponent ist. Die Primzahl selbst ist 2^q − 1. Somit ist die kleinste Primzahl in untenstehender Tabelle 2^1398269 − 1.

Mn ist der Rang der Mersenne-Primzahl gemäß ihrem Exponenten. M48 ist die größte Mersenne-Primzahl, für die ihr Rang bewiesen wurde, da alle kleineren Kandidaten doppelt geprüft wurden.

Entdeckungsdatum	Primzahl	Stellen	Name	Entdecker	Maschine
13. November 1996	M1398269	420.921	M35	Joel Armengaud[22]	Pentium (90 MHz)
24. August 1997	M2976221	895.932	M36	Gordon Spence[22]	Pentium (100 MHz)
27. Januar 1998	M3021377	909.526	M37	Roland Clarkson[22]	Pentium (200 MHz)
1. Juni 1999	M6972593	2.098.960	M38	Nayan Hajratwala[22]	Pentium (350 MHz)
14. November 2001	M13466917	4.053.946	M39	Michael Cameron[22]	AMD Thunderbird (800 MHz)
17. November 2003	M20996011	6.320.430	M40	Michael Shafer[22]	Pentium (2 GHz)
15. Mai 2004	M24036583	7.235.733	M41	Josh Findley[22]	Pentium 4 (2,4 GHz)
18. Februar 2005	M25964951	7.816.230	M42	Martin Nowak[22]	Pentium 4 (2,4 GHz)
15. Dezember 2005	M30402457	9.152.052	M43	Curtis Cooper & Steven Boone[22]	Pentium 4 (2 GHz übertaktet auf 3 GHz)
4. September 2006	M32582657	9.808.358	M44	Curtis Cooper & Steven Boone[22]	Pentium 4 (3 GHz)
23. August 2008	M43112609	12.978.189	M47	Hans-Michael Elvenich[22]	Intel Core 2 Duo E6600 CPU (2,4 GHz)
6. September 2008	M37156667	11.185.272	M45	Odd M. Strindmo[22]	Intel Core 2 Duo (2,83 GHz)
4. Januar 2009	M42643801	12.837.064	M46	Edson Smith[22]	Intel Core 2 Duo (3 GHz)
25. Januar 2013	M57885161	17.425.170	M48	Curtis Cooper[22]	Intel Core 2 Duo (3 GHz)[22]
7. Januar 2016	M74207281	22.338.618	M49?	Curtis Cooper[22]	Intel i7-4790 (3,6 GHz)
26. Dezember 2017	M77232917	23.249.425	M50?	Jon Pace[22]	Intel i5-6600 (3,3 GHz)[22]
7. Dezember 2018	M82589933	24.862.048	M51?	Patrick Laroche[22]	Intel i5-4590T (2,0 GHz)[22][23][24]
12. Oktober 2024	M136279841	41.024.320	M52?	Luke Durant[22]	NVIDIA A100 GPU[22]

Immer wenn eine mögliche Primzahl an den Server gemeldet wird, wird vor deren Verkündung eine Verifikation (Zweittest) durchgeführt, um Fehlmeldungen zu vermeiden: 2003 beispielsweise wurde eine falsche als 40. Mersenne-Primzahl gemeldet.

Die Software

→ Hauptartikel: MPrime

Das Projekt verwendet für die Suche nach Mersenne-Primzahlen vorwiegend den computerbasierten Lucas-Lehmer-Test (LL-Test) von Édouard Lucas und Derrick Henry Lehmer,^[25] ein Algorithmus, der auf den Test von Mersenne-Primzahlen spezialisiert und insbesondere effizient in binären Computersystemen ist.

Vor dem eigentlichen LL-Test erfolgt eine kurze Phase mit Probedivisionen auf enthaltene kleine Faktoren. Computerisierte Probedivisionen dauern im Vergleich zu den LL-Tests sehr viel kürzer, nur Tage statt Wochen. Dadurch können schnell und effizient Mersenne-Primzahl-Kandidaten aussortiert werden, wenn für diese kleine Faktoren gefunden werden können. Dieses effiziente Eliminieren von Kandidaten wird regelmäßig für eine große Zahl von Kandidaten erfüllt, so ist etwa jede dritte Kandidatin durch drei teilbar, jede fünfte durch fünf usw. John M. Pollards P − 1-Algorithmus wird für die Suche nach enthaltenen größeren Faktoren in Mersenne-Primzahl-Kandidaten verwendet.

Obwohl der GIMPS-Quelltext frei verfügbar ist, gilt die Software nicht als freie Software, da sich Benutzer an die Projektbedingungen, die GIMPS End User License Agreement (EULA)^[26] und die GIMPS Terms and Conditions of Use (TCU)^[27] binden müssen, dies gilt insbesondere bei der Suche nach Mersenne-Primzahlen.

Der Lucas-Lehmer-Test

→ Hauptartikel: Lucas-Lehmer-Test

Dieser Test ist ein speziell auf Mersenne-Zahlen zugeschnittener Primzahltest, der auf Arbeiten von Édouard Lucas aus der Zeit 1870–1876 beruht und im Jahr 1930 von Derrick Henry Lehmer ergänzt wurde.

Er funktioniert wie folgt:

Sei ${\displaystyle p}$ ungerade und prim. Die Folge ${\displaystyle S(k)}$ sei definiert durch ${\displaystyle S(1)=4,S(k+1)=S(k)^{2}-2}$.

Dann gilt: ${\displaystyle M_{p}=2^{p}-1}$ ist genau dann eine Primzahl, wenn ${\displaystyle S(p-1)}$ durch ${\displaystyle M_{p}}$ teilbar ist.

Literatur

• Günter M. Ziegler: The Great Prime Number Record Races. In: Notices of the AMS. Band 51, 2004, S. 414–416 (ams.org [PDF; abgerufen am 10. Dezember 2020]). 

Siehe auch

• Liste der Projekte verteilten Rechnens
• Volunteer-Computing

Einzelnachweise

1. PrimeNet Statistics. Abgerufen am 22. Februar 2019. 
2. GIMPS – Free Prime95 software downloads – PrimeNet. Abgerufen am 22. Februar 2019. 
3. Mlucas – A portable program for Lucas-Lehmer tests. Abgerufen am 22. Februar 2019. 
4. Glucas – Yet Another FFT / Wiki / Home. Abgerufen am 22. Februar 2019. 
5. Mersenne Prime Discovery – 2^6972593-1 is Prime! Abgerufen am 22. Februar 2019. 
6. Electronic Frontier Foundation. Abgerufen am 22. Februar 2019 (englisch). 
7. Titanic Primes Raced to Win $100,000 Research Award. Abgerufen am 22. Februar 2019. 
8. zunächst war dies die 45. bekannte Mersenne-Primzahl; kurz danach wurden jedoch noch zwei kleinere Mersenne-Primzahlen (M_37,156,667 ^{und M}_42,643,801^{) gefunden.}
9. Press Release: Record 12-Million-Digit Prime Number Nets $100,000 Prize. 14. Oktober 2009, abgerufen am 22. Februar 2019 (englisch). 
10. EFF Cooperative Computing Awards. 29. Februar 2008, abgerufen am 22. Februar 2019 (englisch). 
11. 332.2M – 333.9M (aka 100M digit range) – mersenneforum.org. Abgerufen am 22. Februar 2019. 
12. PrimeNet Activity Summary Aggregate Computing Power last 30 days, actual 86,107 TFLOP/sec; Webzugriff am 14. Februar 2013.
13. PrimeNet Activity Summary Aggregate Computing Power last 30 days, actual 86.107 TFLOP/sec; abgerufen am 5. April 2012.
14. TOP500 per November 2011; nach dem 'HP DL160 Cluster G6' von Hewlett-Packard – HP DL160 mit 87,095 TFLOP/s (R max).
15. Top500 List – November 2016 | TOP500 Supercomputer Sites. In: www.top500.org. Archiviert vom Original (nicht mehr online verfügbar) am 3. Januar 2017; abgerufen am 7. Januar 2017. 
16. George Woltman: The Mersenne Newsletter, issue #1. (txt) Great Internet Mersenne Prime Search (GIMPS), 24. Februar 1996, abgerufen am 16. Juni 2009. 
17. George Woltman: The Mersenne Newsletter, issue #9. (txt) GIMPS, 15. Januar 1997, abgerufen am 16. Juni 2009. 
18. mersenneforum.org – View Single Post – Trial Factoring vs. LL-testing. Abgerufen am 22. Februar 2019. 
19. The Mersenne Newsletter, Issue #9. Abgerufen am 25. August 2009.
20. George Woltman: The Mersenne Newsletter, issue #3. (txt) GIMPS, 12. April 1996, abgerufen am 16. Juni 2009. 
21. George Woltman: The Mersenne Newsletter, issue #8. (txt) GIMPS, 23. November 1996, abgerufen am 16. Juni 2009. 
22. List of Known Mersenne Prime Numbers. Great Internet Mersenne Prime Search, abgerufen am 21. Oktober 2024. 
23. Mersenne Prime Discovery – 2^82589933-1 is Prime! 21. Dezember 2018, abgerufen am 22. Dezember 2018. 
24. heise online: Computer in Florida findet neue größte Primzahl. 22. Dezember 2018, abgerufen am 22. Dezember 2018. 
25. What are Mersenne primes? How are they useful? – GIMPS FAQ Page
26. GIMPS End User License Agreement. Mersenne Research Inc, abgerufen am 25. April 2019 (englisch). 
27. GIMPS Terms and Conditions of Use. Mersenne Research Inc, abgerufen am 25. April 2019 (englisch). 

Weblinks

• GIMPS Home Page
• GIMPS Forum
• GIMPS PrimeNet Server