Numerator: Zwei neue Rekord-Primzahlen entdeckt

Sie haben mehr als zehn Millionen Stellen: Mit Computerhilfe wurden zwei weitere Primzahlen entdeckt - ein neuer Rekord. Bei der Jagd nach immer größeren unteilbaren Ziffern geht es um sichere Datenverschlüsselung. Und um 100.000 Dollar.

Es ist die wohl seltsamste Lotterie des Internets, an der Mathematik-begeisterte Surfer seit Jahren teilnehmen. Nachdem sie eine Software namens Gimps installiert haben, bekommt ihr Computer von einem Server eine achtstellige Primzahl p zugeteilt. Diese ist, wie jede Primzahl, nur durch eins und sich selbst teilbar. Das Programm berechnet dann die Zahl 2^p - 1 und überprüft, ob es sich dabei wiederum um eine Primzahl handelt. Das ist höchst mühselig: Mit derartigen Berechnungen ist selbst ein moderner PC tagelang beschäftigt.

Welche achtstellige Primzahl man als Teilnehmer des Gimps-Projekts  zur Überprüfung bekommt, ist eine Frage des Zufalls. Wer großes Glück hat und dabei eine neue Primzahl findet, kann 100.000 Dollar gewinnen. Diese Summe hat die Electronic Frontier Foundation (EFF) für die Entdeckung der ersten Primzahl mit mindestens zehn Millionen Stellen ausgelobt . Der Preis geht an die Person, deren Rechner die Zahl ausfindig gemacht hat.

Jetzt gibt es gleich zwei Anwärter auf die 100.000 Dollar. Am 23. August und 6. September meldete jeweils ein Computer, eine neue sogenannte Mersenne-Primzahl gefunden zu haben. Beide Primzahlen haben nach Angaben der Deutschen Mathematiker-Vereinigung mehr als die von der EFF geforderten zehn Millionen Stellen, einer der Rechner soll sogar in Deutschland stehen. Bis zum 14. September wird es eine zweite Überprüfung der Zahlen geben - danach dürfte der Gewinner der Prämie feststehen.

Gewissheit ist schwer zu erlangen

Mersenne-Primzahlen lassen sich in der Form 2^p - 1 darstellen, wobei auch der Exponent p eine Primzahl ist. Für sie interessieren sich Mathematiker besonders, denn Mersenne-Primzahlen haben einen entscheidenden Vorteil: Man kann sie vergleichsweise leicht finden.

Ein- und zweistellige Primzahlen wie 3, 5, 7 und 11 kennt man aus der Schule. Die Suche nach großen Primzahlen mit Hunderten, Tausenden oder Millionen Stellen ist ungleich schwieriger. Das liegt daran, dass man großen Zahlen ihre Teiler schlicht nicht ansieht - eine nicht nur für Mathematiker missliche Situation.

"Für Mersenne-Zahlen gibt es ein vergleichsweise effizientes Verfahren, um zu überprüfen, ob es eine Primzahl ist oder nicht", sagt Florian Hess, Mathematiker an der TU Berlin. Bei anderen zufällig ausgewählten Zahlen sei die Sache ungleich schwieriger. In einigen Tagen Rechenzeit - wie bei Mersenne-Zahlen üblich - könne man dann nicht mehr feststellen, ob die Zahl weitere Teiler außer Eins und sich selbst habe.

Sicherheit und Rechenpower

Primzahlen faszinieren die Menschheit seit Jahrtausenden - eine echte Anwendung gibt es aber erst, seit leistungsfähige Computer verfügbar sind. Bei der Verschlüsselung von Daten spielen Primzahlen nämlich eine entscheidende Rolle. Das sogenannte RSA-Verfahren, mit dem beispielsweise Banken im Internet verschlüsselt kommunizieren, nutzt die Tatsache aus, dass eine große Zahl nur mit extrem großem Aufwand in ihre Primfaktoren zerlegt werden kann.

Die RSA-Verschlüsselung ist nicht kompliziert: Die Bank multipliziert zwei 150- oder besser noch 300-stellige Primzahlen miteinander. Das Produkt geht in den sogenannten öffentlichen Schlüssel ein, mit dem der Bankkunde die an den Bankserver zu sendenden Daten verschlüsselt. Dies erledigt der Webbrowser von allein. "90 Prozent aller Sicherheitsanwendungen im Internet beruhen auf diesem Verfahren", sagt der Berliner Mathematiker Florian Hess. Zum Entschlüsseln benötigt man entweder die beiden Primzahlen, welche die Bank folgerichtig geheim halten muss, oder aber einen gigantischen Rechnerpark.

Die Sicherheit dieser Form der Kryptographie beruht allein darauf, dass das Knacken des Schlüssels zu viel Rechenpower und Zeit benötigt. Weil Computer immer leistungsfähiger werden, müssen in der Kryptografie immer größere Primzahlen zum Einsatz kommen - daher ist die Suche nach immer größeren Primzahlen auch von ganz praktischem Interesse.

"Eines der größten ungelösten Probleme der Mathematik"

Machen die nun entdeckten zwei neuen größten Primzahlen die Kommunikation im Internet weniger sicher? Nein, lautet die Antwort von Günter Ziegler, Präsident der Deutschen Mathematiker-Vereinigung. "Die Datensicherheit im Internet ist durch den jetzigen Rekord nicht gefährdet", erklärt er. Der Grund dafür liegt in der bereits beschriebenen Besonderheit der Mersenne-Zahlen: Ob sie prim sind oder nicht, kann ein Computer relativ schnell prüfen. Das ist bei anderen, von Banken genutzten Zahlen nicht der Fall.

Einige große Fragen zu Primzahlen haben Mathematiker bereits in den vergangenen Jahrhunderten beantworten können. So zum Beispiel jene nach der Menge der existierenden Primzahlen: Es sind unendlich viele.

Der Beweis ist simpel: Man nimmt an, es gibt nur endlich viele Primzahlen p₁, p₂, p₃, … p_n. Dann multipliziert man alle diese n Primzahlen miteinander und addiert 1 dazu. Das Ergebnis ist eine Zahl, die durch keine der n Primzahlen teilbar ist. Es kann sich dabei nur um eine neue Primzahl, oder um das Produkt aus mindestens zwei neuen Primzahlen handeln. Damit ist die Annahme, es gebe nur endlich viele Primzahlen, widerlegt.

Ein anderes, bislang aber ungelöstes Problem, bei dem auch Primzahlen eine Rolle spielen, ist die sogenannte Riemannsche Vermutung. Der deutsche Mathematiker Bernhard Riemann hatte vor mehr als 150 Jahren die Hypothese aufgestellt, dass die Nullstellen der sogenannten Riemannschen Zetafunktion auf einer Geraden liegen. "Diese Funktion kann mithilfe von Primzahlen definiert werden", erklärt Florian Hess von der TU Berlin. Riemanns Vermutung sei mit Computern für Millionen von Nullstellen zwar bereits bewiesen worden, der endgültige Beweis stehe aber noch aus. "Das ist eines der größten ungelösten Probleme der Mathematik", sagt Hess.

Eine Lösung ist auch deshalb von großem Interesse, weil sich mit der Zetafunktion die Laufzeiten von Algorithmen abschätzen lassen - äußerst hilfreich bei aufwendigen Berechnungen. Wer die Riemannsche Vermutung beweist, wird jedoch nicht nur berühmt, sondern auch reich. Eine Million Dollar hat das Clay Mathematics Institute als Preis ausgesetzt.

Im Vergleich dazu ist die Suche nach immer größeren Primzahlen schlecht bezahlt - allerdings muss sich der Gewinner dabei auch nicht den eigenen Kopf zerbrechen. Die Arbeit übernimmt die Gimps-Software.

Ergänzung: Inzwischen steht fest, dass das Preisgeld von 100.000 Dollar nach Los Angeles geht. Am 23. August hatte ein Team von der University of California die größere der beiden Primzahlen, nämlich 2^43.112.609-1, mit genau 12.978.189 Stellen gefunden. Zwei Wochen später, am 6. September, entdeckte der Kölner Hans-Michael Elvenichs Rechner die zweite Primzahl: 2^37.156.667-1. Sie hat 11.185.272 Stellen.