Suche nach Primzahlen: Die Nächste, bitte!

Primzahlen sind sind essenziell für die Zahlentheorie und sind nützlich zur Verschlüsselung. Nun wurde eine neue größte Primzahl gefunden.

Die längste Primzahl, 41 Millionen Zahlen, passt leider nicht auf diesen Zettel   Foto: Viola Lopes/dpa

Luke Durant aus Kalifornien ist zurzeit der Held unter den Primzahlnerds. Denn der Hardware-Ingenieur und „Hobbymathematiker“ – wie er von den meisten Medien bezeichnet wird – hat vor wenigen Wochen, am 12. Oktober, nicht nur eine neue, sondern die bislang größte bekannte Primzahl entdeckt. Sie lautet: 2^136.279.841–1. Heißt, man multipliziert 136.279.841-mal die 2 mit sich selbst und zieht 1 ab. Das Ergebnis ist eine Zahl, die über 41 Millionen Ziffern lang ist. Wollte man die Zahl etwa in einer taz abdrucken, wäre die Zeitung dick wie ein Buch und hätte über 2.000 Seiten.

Primzahlen spielen in der Mathematik, vor allem in der Zahlentheorie, schon seit Jahrtausenden eine ganz besondere Rolle. Denn sie haben nur zwei Teiler, sind also nur durch sich selbst und eins teilbar. Teilbar bedeutet, dass beim Dividieren kein Rest übrigbleibt. Die bekanntesten Primzahlen, die viele noch aus der Schulzeit kennen, lauten wohl 2, 3, 5, 7 oder 11.

Größenmäßig liegen zwischen ihnen und Durants Zahl Welten. „Seine“ Primzahl hat der 36-Jährige im Rahmen des Primzahlprojekts Gimps entdeckt, bei dem er sich vergangenes Jahr anmeldete. Das Projekt glaubt, Primzahlen finden, das ist Gemeinschaftssache. Vor allem, weil große Primzahlen zu berechnen unglaublich viel Rechenleistung erfordert. Die Idee von Gimps ist es, Privatpersonen und Organisationen zusammenzubringen, die ihre Rechenpower zur Verfügung stellen.

Mit diesem Ansatz hat seit 1996 das Projekt insgesamt 18 neue Primzahlen berechnet. Die letzte Primzahlentdeckung vor der Durants war schon sechs Jahre her. Dass er eine weitere, so große Primzahl gefunden hat, hat vor allem mit einem Durchbruch zu tun, der die Rechenleistung zur Berechnung nochmals extrem erhöht hat. Dazu später mehr. Wer – wie Durant – fündig wird bei der Primzahlsuche erhält vom Gimps 3.000 US-Dollar Belohnung.

Doch, neben der kleinen Prämie, was macht die Faszination Primzahl aus? Warum geben Privatpersonen ihre Rechenleistung dafür her und was ist der Reiz an der nerdigen Suche nach der nächsten großen Primzahl?

Besonders interessant sind Primzahlen für die Zahlentheorie. Jede ganze Zahl lässt sich als ein Produkt von Primzahlen darstellen und damit auf eine einzige Art und Weise in Primzahlen zerlegen. Das ist die sogenannte Primfaktorzerlegung. Zum Beispiel ist 99 = 3² x 11. Primzahlen bilden also die kleinsten Grundbausteine der ganzen Zahlen, fast wie Zellen einen Körper aufbauen oder Atome Moleküle bilden.

Primzahlen sind der Schlüssel

Noch interessanter wurden die Primzahlen in der zweiten Hälfte des 20. Jahrhunderts innerhalb der Kryptografie, also in der Wissenschaft der Verschlüsselung, des „geheimen Schreibens“. Besonders gebräuchlich ist heute etwa das RSA-Verschlüsselungsverfahren. Dieses nutzt zwei unterschiedliche Schlüssel, einen öffentlichen zum Verschlüsseln von Daten und einen privaten zum Entschlüsseln von Daten, wie Nachrichten oder Signaturen. Verschlüsselt wird bei dem Verfahren mithilfe von Primzahlen und einem Trick.

Die Rechnung funktioniert nämlich wie eine Falltür, heißt, in die eine Richtung sehr leicht zu lösen, in die andere extrem schwer. Um die jeweiligen Schlüssel zu berechnen, werden zwei eher große Primzahlen zu einem Produkt multipliziert. Das ist einfach. Nur zum Entschlüsseln – ohne Zugang zu dem privaten Schlüssel – müsste man wieder die einzelnen Primfaktoren zurückrechnen. Um den Schlüssel zu knacken, müsste man dafür alle Primzahlen durchgehen, die kleiner als die Hälfte des bekannten Produkts sind. Der Rechenaufwand, um dies zu tun, ist heutzutage noch zu hoch, was solche Verschlüsselungen auf herkömmlichen Computern meist unknackbar macht.

Die Beschäftigung mit Primzahlen hat in der Mathematik eine lange Tradition. Schon in der Antike, im dritten Jahrhundert vor Christus, bewies der Mathematiker Euklid von Alexandria, dass es unendlich viele Primzahlen gibt. Interessanterweise kannte man zu dieser Zeit das Konzept der Unendlichkeit noch nicht. Euklid bewies vielmehr, dass man aus endlich vielen Primzahlen immer eine weitere, größere Primzahl konstruieren kann. Somit gibt es – in unseren heutigen Worten – unendlich viele. Formal gibt es also kein Problem, immer weiterzusuchen nach der nächsten Primzahl. Doch die Primzahlen wirklich zu berechnen ist ab einer gewissen Größe gar nicht so einfach. Schnell kann es an der Rechenleistung des Computers scheitern.

Deshalb widmet sich Gimps einer besonderen Art der Primzahlen, den sogenannten Mersenne-Primzahlen. Dafür steht auch ihre Abkürzung, ausgeschrieben heißt das Projekt Great Internet Mersenne Prime Search. Mersenne-Primzahlen haben eine besonders einfache Darstellungsform, als M_p=2^p–1. Dabei ist p eine Primzahl. Damit sind sie vergleichbar einfach zu berechnen. Der Name geht auf den französischen Mathematiker und Mönch Marin Mersenne zurück, der sich Anfang des 17. Jahrhunderts mit dieser Darstellungsart von Primzahlen beschäftigte. Und eine Liste solcher Zahlen erstellte.

Die einfachste so zu beschreibende Primzahl ist wohl die 3 als 2²–1. Bis heute sind 52 Mersenne-Primzahlen bekannt. Denn ganz so einfach ist es nicht. Nicht alle Zahlen, die bei der Formel von M_p rauskommen, sind auch Primzahlen. So ist zum Beispiel M₁₁=2047 nicht prim, da sie unter anderem durch 23 teilbar ist. Und andersherum sind auf keinen Fall alle Primzahlen als 2^p –1 darstellbar. Man versuche das zum Beispiel mal mit der 5. Unmöglich.

Die Berechnung von möglichen Mersenne-Primzahlen ist somit eine mögliche strukturierte Herangehensweise, um bei der Primzahlsuche nicht völlig im Dunkeln zu stochern. Es muss aber immer überprüft werden, ob eine berechnete Mersenne-Zahl auch wirklich prim ist.

Trotz des Nutzens von Primzahlen in der Verschlüsselung bleibt laut dem Mathematiker Kevin Buzzard vom Imperial College London die Entdeckung der bislang größten Primzahl durch Luke Durant vor allem eine Spielerei. Praktische Anwendung habe sie im Moment keine. Um sie in der Kryptografie zu nutzen, ist sie (noch) zu groß.

Mehr Rechenpower

Luke Durants Fund hat aber vor allem gezeigt, dass auch in der Rechenpower noch einiges geht. In seiner Entdeckung hat er einen riesigen Fortschritt vollbracht. Ehemals hat Luke Durant beim Hardwareunternehmen Nvidia gearbeitet, das unter anderem Grafikkarten herstellt. Die waren sein Kniff. Sie verhalfen ihm zu noch mehr Leistungsfähigkeit bei der Berechnung und Prüfung seiner möglichen Primzahlen.

Indem er mit Grafikprozessoren arbeitete und eine Infrastruktur entwickelte, um die von Gimps zur Verfügung gestellte Software auf vielen Servern auszuführen und zu warten. Damit baute er eine Art „Cloud-Supercomputer“. Zum Zeitpunkt der Entdeckung bestand dieser aus Tausenden von Server-Grafikprozessoren, verteilt über 24 Rechenzentrums­regionen in 17 Ländern.

Für Zahlentheoretiker und Hobbymathematiker bleiben aber weiterhin viele Fragen offen. Gibt es zwischen der letzten und der neuen entdeckten Mersenne-Primzahl noch weitere (Mersenne-)Primzahlen? Und gibt es überhaupt unendlich viele solcher speziell darstellbaren Primzahlen? Und wie verhält es sich mit ihrer Verteilung und Häufigkeit?

Letzteres ist die zentrale Frage hinter der weltbekannten „Riemannsche Vermutung“. Bernhard Riemanns Aussage von 1859 über die zufällige Verteilung und Häufigkeit von Primzahlen ist bis heute unbewiesen. Die Annahme des deutschen Mathematikers gilt als bedeutendstes ungelöstes Problem der reinen Mathematik. Wer einen schlüssigen Beweis liefert, bekommt vom Mathematikinstitut der Universität Cambridge ein Preisgeld von einer Million US-Dollar.