39. Mersenne-Primzahl entdeckt

Die in dem Projekt "Great Internet Mersenne Prime Search" zusammengeschlossene Internetgemeinde war wieder einmal erfolgreich.

In Pocket speichern vorlesen Druckansicht 290 Kommentare lesen
Lesezeit: 3 Min.
Von
  • Andreas Stiller

Die in dem GIMPS-Projekt (Great Internet Mersenne Prime Search) zusammengeschlossene Internetgemeinde war wieder einmal erfolgreich: 213466917-1, eine Zahl mit rund 4 Millionen Stellen, ist jetzt die größte bekannte Primzahl. Bereits am 14. November hatte der Rechner (ein Athlon 800) des kanadischen Studenten Michael Cameron dieses Ergebnis nach 45-tägiger Rechenarbeit ausgespuckt. Es dauerte dann aber noch bis zum heutigen Nikolaustag, bis Scott Kurowski von entropia das Ergebnis auf einem andern Rechner mit einem anderen Algorithmus verifizieren konnte. Die teilweise schon vorab verbreiteten Erfolgsmeldungen waren also noch etwas verfrüht.

Mit etwa 2,5 Billionen Gleitkommaoperationen pro Sekunde (TeraFlops) hat das Rechennetz (primenet) der GIMPS-Mithelfer etwa so viel Rechenpower wie die besten derzeitigen Supercomputer (es stünde in der Top500-Liste etwa auf Platz Vier). IBM, der Spitzenreiter in dieser Rangliste, ist übrigens just eine Partnerschaft mit dem Primnet-Betreiber entropia eingegangen.

An dem von George Woltman ins Leben gerufenen GIMPS-Projekt, das nunmehr zum fünften Male in Folge die größte bekannte Primzahl ermittelte, beteiligen sich weltweit etwa 130.000 "Freiwillige", die meist die Idle-Zeit (wenn also der Rechner gerade nichts zu tun hat) zur Durchführung der von primenet koordinierten Tests nutzen. Die Mersenneschen Zahlen der Form 2p-1 eigenen sich besonders für die Suche nach großen Primzahlen, da es hierfür spezielle Kriterien gibt, die man vergleichsweise "schnell" überprüfen kann. Ein klassischer Versuch -- etwa nach der Methode des Siebs des Eratostenes -- würde demgegenüber nahezu "unendlich" dauern. Die GIMPS-Software verwendet den Primtest von Lucas-Lehmer, bei dem heutzutage die schnelle IBDWT (Irrational-Based Discret Weighted Transform) von Dr. Richard Crandall für die Quadrierung modulo 2p-1 zum Einsatz kommt. Diese entwickelte Crandall noch in seiner Zeit als Wissenschaftler bei Apple und Next; er beschreibt sie in seinem jüngst beim Wissenschaftsverlag Springer erschienen Buch Prime numbers.

Die Beschäftigung mit solchen Primzahlen kostet zwar Rechenzeit und Strom, kann sich aber durchaus lohnen, denn hierfür sind oft Prämien ausgesetzt. So erhielt der Entdecker von M38 von der Electronic Frontier Foundation 50.000 US-Dollar für die Entdeckung der ersten Primzahl mit mehr als eine Millionen Stellen. Die nächste Prämienstufe von 100.000 US-Dollar ist für eine Primzahl mit 10 Millionen Stellen ausgelobt. Die hat Michael Cameron mit M39 noch nicht ganz erreicht, da muss die GIMPS-Gemeinde wohl noch ein bisschen weiterrechnen. Die neueste Version V21 der GIMPS-Software unterstützt übrigens auch SSE2 des Pentium 4, was sie um gut Faktor drei beschleunigt. Das zeigt mal wieder, welche Performance-Steigerung durch ausgeklügelte Handoptimierung möglich ist -- und verhilft den Mitstreitern bei GIMPS möglicherweise zu schnellerem Erfolg bei der weiteren Suche. (as)