Great Internet Mersenne Prime Search

Great Internet Mersenne Prime Search

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-Server. GIMPS ist als Mersenne Research, Inc. eingetragen. Es war der erste umfangreiche Einsatz von verteiltem Rechnen über das Internet für Forschungszwecke.

Inhaltsverzeichnis

Das GIMPS Forschungsprojekt

GIMPS bietet weltweit die Beteiligung an einem Projekt für Verteiltes Rechnen an, um Mersenne-Primzahlen zu finden. Die erforderliche Software, die George Woltman ab 1996 programmierte, kann von der GIMPS-Download-Webseite 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, Mac OS X, Linux 64-bit und 32-bit, FreeBSD und PC-BSD 64-bit und 32-bit. Für andere Computerplattformen stehen die Programme Mlucas und Glucas zur Verfügung. Nach der Installation der jeweiligen Prime95 Softwareversion auf einem Computer kommuniziert diese im laufenden Betrieb mit dem Internet PrimeNet Server von Scott Kurowski um u.a. (Zwischen-) Ergebnisse zu registrieren, eliminierte Mersenne-Primzahlkandidaten zu speichern und GIMPS Nutzerdaten zu verwalten. Der PrimeNet Server ist zusammen mit den lose gekoppelten Computern, die Prime95 oder MPrime ausführen, ein Grid-Computing Netzwerk für Verteiltes Rechnen, bei der ein virtueller Supercomputer für die rechenintensive wissenschaftlich-mathematische Suche nach Mersenne-Primzahlen entsteht.

Der GIMPS Supercomputer erzielte am 6. April 2000 einen ersten Preis der Electronic Frontier Foundation (EFF) von 50.000 US$ für das erste Auffinden einer Primzahl mit mehr als einer Million Ziffern. Es handelt sich um die 38. Mersenne-Primzahl M(6.972.593)[1], die 2.098.960 Stellen hat und am 1. Juni 1999 mit einem 350 MHz IBM Aptiva PC gefunden wurde. Der Preis ging zu Teilen an GIMPS und Nayan Hajratwala aus Plymouth, Michigan[2]. Edson Smith[3] fand die 47. bekannte Mersenne-Primzahl M(42.643.801), 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 Auffinden einer ersten Primzahl mit mehr als zehn Millionen Ziffern von 100.000 US$[4], er ging am 14. Oktober 2009 zu Teilen an GIMPS und das Mathematikdepartment der University of California in Los Angeles (UCLA).

Mit 150.00 US$ für das Auffinden der ersten Primzahl mit mehr als 100 Millionen Ziffern (100.000.000) und 250.00 US$ für das erste Finden einer Primzahl mit mehr als 1 Milliarde Ziffern (1.000.000.000) sind zwei weitere Preise, die so genannten Cooperative Computing Awards der EFF[5] ausgeschrieben. Der GIMPS Grid-Supercomputer beteilig sich daran[6], in der Prime95 Software und auf dem PrimeNet Server kann die Suche nach 100 Millionen zifferigen Mersenne-Primzahlen eingestellt werden.

Status

Per Oktober 2010 hat GIMPS einen Durchsatz von ca. 50 Teraflops,[7] was GIMPS theoretisch einen Platz unter den Liste der leistungsstärksten Computer der Welt einbringt. Mitte 2008 waren es ca. 30 Teraflops, Mitte 2006 ca. 20 Teraflops und zu Anfang 2004 ca. 14 Teraflops.

Geschichte

Das GIMPS Projekt begann im Januar 1996 mit einem Programm, das auf i386-Computern lief.[8][9] Der erste getestete Exponent damals war M859.433[10]. Der Name für das Projekt wurde von Luther Welsh gefunden, einer der ersten Teilnehmer und der Entdecker der 29. Mersenne-Primzahl[11]. Innerhalb weniger Monate hatten sich 1996 mehrere dutzend Personen angeschlossen, über tausend am Ende des ersten Jahres.[9][12] Joel Armengaud, ein Teilnehmer, entdeckte die Primalität von M1.398.269 am 13. November 1996.[13]

Gefundene Primzahlen

Siehe: Mersenne-Primzahl

Bis dato (Oktober 2010) hat das Projekt insgesamt 13 Mersenne-Primzahlen gefunden, wovon 11 zu ihrem Entdeckungszeitpunkt die weltweit größten bekannten waren. Die aktuell größte ist 243.112.609 − 1 (oder kurz M43.112.609). Diese Primzahl wurde am 23. August 2008 von Edson Smith an der University of California, Los Angeles (UCLA) entdeckt[14]. Diese Primzahl bedeutete für GIMPS den Gewinn des $100.000 Preises der Electronic Frontier Foundation für die Entdeckung einer Primzahl mit mehr als 10 Millionen Stellen[15].

Alle Primzahlen haben die Form Mq, wobei q der prime Exponent ist. Die Primzahl selbst ist 2q − 1,. Somit ist die kleinste Primzahl in untenstehender Tabelle 21398269 − 1.

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

Entdeckungsdatum Primzahl Stellen Name Maschine
13. November 1996 M1398269 420.921 M35 Pentium (90 MHz)
24. August 1997 M2976221 895.932 M36 Pentium (100 MHz)
27. Januar 1998 M3021377 909.526 M37 Pentium (200 MHz)
1. Juni 1999 M6972593 2.098.960 M38 Pentium (350 MHz)
14. November 2001 M13466917 4.053.946 M39 AMD Thunderbird (800 MHz)
17. November 2003 M20996011 6.320.430 M40 Pentium (2 GHz)
15. Mai 2004 M24036583 7.235.733 M41 ? Pentium 4 (2,4 GHz)
18. Februar 2005 M25964951 7.816.230 M42 ? Pentium 4 (2,4 GHz)
15. Dezember 2005 M30402457 9.152.052 M43 ? Pentium 4 (2 GHz übertaktet auf 3 GHz)
4. September 2006 M32582657 9.808.358 M44 ? Pentium 4 (3 GHz)
23. August 2008 M43112609 12.978.189 M47 ? Intel Core 2 Duo E6600 CPU (2,4 GHz)
6. September 2008 M37156667 11.185.272 M45 ?
12. April 2009 M42643801 12.837.064 M46 ? Intel Core 2 Duo (3 GHz)

Die Zahl M43112609 hat 12.978.189 Stellen. Bei 50 Zeilen pro Seite und 75 Zeichen pro Linie würde ein gedrucktes Buch mit 3.461 Seiten benötigt, um die Zahl darzustellen.

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 ein false positive 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[16], 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 zweite Kandidatin durch zwei teilbar, jede dritte durch drei, 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) und die GIMPS Terms and Conditions of Use (TCU) 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 Lehmer ergänzt wurde.

Er funktioniert wie folgt:

Sei p ungerade und prim. Die Folge S(k) sei definiert durch S(1) = 4, S(k+1) = S(k)2–2.
Dann gilt: Mp = 2p–1 ist genau dann eine Primzahl, wenn S(p–1) durch Mp teilbar ist.

Siehe auch

Einzelnachweise

  1. ↑ GIMPS Finds First Million-Digit Prime, Stakes Claim to $50,000 EFF Award
  2. ↑ EFF Gives $50,000 to Finder of Largest Known Prime Number
  3. ↑ Titanic Primes Raced to Win $100,000 Research Award
  4. ↑ Record 12-Million-Digit Prime Number Nets $100,000 Prize - Mersenne.org Wins EFF's Cooperative Computing Award
  5. ↑ EFF Cooperative Computing Awards
  6. ↑ 100M digit range (mersenneforum.org)
  7. ↑ PrimeNet Activity Summary
  8. ↑ George Woltman (February 24, 1996): The Mersenne Newsletter, issue #1 (txt). Great Internet Mersenne Prime Search (GIMPS). Abgerufen am 16. Juni 2009.
  9. ↑ a b George Woltman (January 15, 1997): The Mersenne Newsletter, issue #9 (txt). GIMPS. Abgerufen am 16. Juni 2009.
  10. ↑ Bekanntgabe von M859.433 (mersenneforum.org)
  11. ↑ The Mersenne Newsletter, Issue #9. Abgerufen am 25. August 2009.
  12. ↑ George Woltman (April 12, 1996): The Mersenne Newsletter, issue #3 (txt). GIMPS. Abgerufen am 16. Juni 2009.
  13. ↑ George Woltman (November 23, 1996): The Mersenne Newsletter, issue #8 (txt). GIMPS. Abgerufen am 16. Juni 2009.
  14. ↑ GIMPS Homepage
  15. ↑ Record 12-Million-Digit Prime Number Nets $100,000 Prize: Mersenne.org Wins EFF's Cooperative Computing Award
  16. ↑ What are Mersenne primes? How are they useful? - GIMPS FAQ Page

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужна курсовая?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Great internet Mersenne prime search — Le Great Internet Mersenne Prime Search, ou GIMPS, est un projet de calcul partagé où les volontaires utilisent un logiciel client pour chercher les nombres premiers de Mersenne. Le projet a été fondé par George Woltman, qui est aussi le créateur …   Wikipédia en Français

  • Great Internet Mersenne Prime Search — (GIMPS, Gran búsqueda de números primos de Mersenne por Internet ) es un proyecto colaborativo de voluntarios que utilizan los programas gratuitos Prime95 y MPrime con el fin de buscar números primos de Mersenne. George Woltman ha fundado el… …   Wikipedia Español

  • Great Internet Mersenne Prime Search — The Great Internet Mersenne Prime Search (GIMPS) is a collaborative project of volunteers who use freely available computer software to search for Mersenne prime numbers. The project was founded by George Woltman, who also wrote the software… …   Wikipedia

  • Great Internet Mersenne Prime Search — Le Great Internet Mersenne Prime Search, ou GIMPS, est un projet de calcul partagé où les volontaires utilisent un logiciel client pour chercher les nombres premiers de Mersenne. Le projet a été fondé par George Woltman, qui est aussi le créateur …   Wikipédia en Français

  • Mersenne prime — Named after Marin Mersenne Publication year 1536[1] Author of publication Regius, H. Number of known terms 47 Conjectured number of terms Infinite …   Wikipedia

  • Mersenne prime — Nombre premier de Mersenne Marin Mersenne En mathématiques et plus précisément en arithmétique modulaire, un nombre premier de Mersenne est un nombre premier s écrivant sous la forme 2p 1, p étant premier. Ces nombres premiers doivent leur nom à… …   Wikipédia en Français

  • Prime number — Prime redirects here. For other uses, see Prime (disambiguation). A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is… …   Wikipedia

  • Mersenne-Primzahl — Poststempel mit der 23. Mersenne Primzahl, gefunden 1963 an der UIUC von Donald B. Gillies. Eine Mersenne Zahl ist eine Zahl der Form 2n − 1. Im Speziellen bezeichnet man mit Mn = 2n − 1 die n te Mersenne Zahl. Die ersten acht Mersenne Zahlen Mn… …   Deutsch Wikipedia

  • Mersenne-Primzahlen — Eine Mersenne Zahl ist eine Zahl der Form 2n − 1. Im Speziellen bezeichnet man mit Mn = 2n − 1 die n te Mersenne Zahl. Die Primzahlen unter den Mersenne Zahlen werden Mersenne Primzahlen genannt. Die ersten acht Mersenne Primzahlen Mp sind 3, 7,… …   Deutsch Wikipedia

  • Mersenne-Zahl — Eine Mersenne Zahl ist eine Zahl der Form 2n − 1. Im Speziellen bezeichnet man mit Mn = 2n − 1 die n te Mersenne Zahl. Die Primzahlen unter den Mersenne Zahlen werden Mersenne Primzahlen genannt. Die ersten acht Mersenne Primzahlen Mp sind 3, 7,… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”