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 51 Mersenne-Primzahlen, bei der größten dieser Zahlen, wird die Zahl 2 insgesamt 82.589.933 mal mit sich selbst multipliziert und vom Ergebnis wird 1 abgezogen. Das Resultat ist eine Zahl mit 24.862.048 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 51. 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 51. Mersenne-Primzahl alt und grau werden; nur die Vielzahl der Teilnehmer sichert einen Treffer in überschaubarer Zeit. Die größte derzeit bekannte Primzahl wurde von Patrick Laroche in den USA am 07. Dezember 2018 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

2^82.589.933 -1 die 51. 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 – die Zahl selbst (also: 28) findet bei der Aufsummierung ihrer Teiler übrigens keine Berücksichtigung! Wenn eine neue Mersenne-Primzahl der Form 2^p-1 entdeckt wird, ergibt sich "automatisch" eine neue vollkommene Zahl nach der Formel z = 2^p-1 x 2^p-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 weiß 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 2^p-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, Taktfrequenz, 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:

2⁵-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 2⁷²⁷-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 2^82.589.933-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

bisher gefundene Mersenne-Primzahlen

Anmerkung: Der Bereich oberhalb der 47. Zahl wurde noch nicht vollständig durch Double-Checking überprüft, sodass nicht mit Sicherheit gesagt werden kann, dass die 48. Mersenne-Primzahl auch die 48. Zahl dieser Art ist. Es besteht noch die Möglichkeit, dass kleinere Mersenne-Primzahlen als die Zahl Nr. 48 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 52. 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: 22.12.2018