Neue Primzahl-Rekorde

Fast 2 Jahre herrschte Rekord-Flaute, aber jetzt gab es binnen 2 Wochen gleich zwei neue Weltrekorde. Erinnert irgendwie an Usain Bolt oder Michael Phelps.

Gut, die beiden Namen waren jetzt nur zur Suchmaschinen-Optimierung. Eigentlich geht es in diesem Beitrag neben der Rekord-Meldung darum: was sind Mersenne-Primzahlen, was ist der Lucas-Lehmer-Test, was ist verteiltes Rechnen und wozu braucht man große Primzahlen?

Zunächst zu den aktuellen Rekorden:

Die bisherige Rekordzahl vom 11.9.2006, also ziemlich genau 2 Jahre alt, war 2^32582657-1. (Sie hatte 9,8 Millionen Stellen.)

Das Projekt GIMPS (Great Internet Mersenne Prime Search) kündigte am 23.8. eine neue Rekordzahl an und bereits am 6.9. die nächste Rekordzahl an. In der letzten Woche ist (innerhalb des Projektes) von 3 verschiedenen Rechnern überprüft worden, daß es sich tatsächlich um Primzahlen handelt. GIMPS will in den nächsten Tagen in einer Pressemitteilung die beiden Zahlen (die bisher noch geheimgehalten werden) veröffentlichen.

Übrigens gehen alle Primzahl-Rekorde seit 1996 (bisher 12) auf das Konto von GIMPS. In allen Fällen handelt es sich um Mersenne-Primzahlen.

Was sind Mersenne-Primzahlen?

Als Mersenne-Zahlen bezeichnet man die Zahlen M_n=2ⁿ-1.
Diese sind für Computer-Rechnungen u.a. deshalb gut geeignet, weil sie sich im Binärsystem nur mit 1’en darstellen lassen. (Deshalb läßt sich bei ihnen der Lucas-Lehmer-Primzahltest besonders einfach durchführen – dazu weiter unten.)

Mersenne, ein Theologe des 17. Jahrhunderts, hatte beobachtet, daß die Folge der Mersenne-Zahlen viele Primzahlen enthält. (Mehr über Mersenne und seine Beiträge u.a. zur Akustik hier.)

Die ersten 8 Primzahlen in der Liste der Mersenne-Zahlen sind 3, 7, 31, 127, 8191, 131071, 524287, 2147483647. Bisher waren 44 Mersenne-Primzahlen bekannt, eine vollständige Liste findet man hier. Die neu-entdeckten Zahlen wären dann also die 45. und 46. Mersenne-Primzahl. (Es ist möglich, daß es zwischen der 39. und der 46. Mersenne-Primzahl weitere Primzahlen gibt, daß die Liste in diesem Bereich also noch nicht vollständig ist.)

Warum sucht man gerade unter Mersenne-Zahlen?

Es ist klar, daß M_n=2ⁿ-1 nur dann eine Primzahl sein kann, wenn n selbst eine Primzahl ist. Wenn n sich als Produkt n=pq zerlegen ließe, wäre nämlich (nach der Summenformel für geometrische Reihen):
M_pq=(2^p-1)(2^p(q-1)+2^p(q-2)+…+2^p+1),
womit auch M_pq als Produkt zerlegt wäre.
Zum Beispiel 63=M₆=3 x (16+4+1)=3 x 21, 255=M₈=3 x (64+16+4+1)=3 x 85.

Man braucht also auf der Suche nach Mersenne-Primzahlen für n nur Primzahlen als Werte einzusetzen.
Zusätzlich kann man unter den Primzahlen, die bei Division durch 4 den Rest 3 lassen, die sogenannten Sophie-Germain-Primzahlen (d.h. Primzahlen n, für die auch 2n+1 eine Primzahl ist) weglassen. In diesem Fall ist nämlich M_n durch 2n+1 teilbar.
Zum Beispiel: 2047=M₁₁ ist durch 23 teilbar. (Ausnahme ist hier natürlich 7=M₃: das ist zwar durch 7 teilbar, aber trotzdem eine Primzahl.)

Damit muß man also bei der Suche nach Mersenne-Primzahlen nicht alle Werte von n durchprobieren.

Ein weiterer Grund, gerade unter Mersenne-Zahlen nach Primzahlen zu suchen, ist die (m.W. unbewiesene) Vermutung, daß die relative Häufigkeit von Primzahlen unter den Mersenne-Zahlen deutlich höher ist als unter natürlichen Zahlen im allgemeinen (letztere ist bekanntlich ungefähr ln(x)/x für große x).

Und außerdem braucht man bei Mersenne-Zahlen nur relativ wenige mögliche Teiler zu überprüfen: nach einem Satz von Euler und Fermat kann eine Primzahl p nur dann ein Teiler von M_n sein, wenn p-1 durch n teilbar ist¹ und außerdem p-1 oder p+1 durch 8 teilbar ist. Die erste Bedingung verringert die Anzahl der zu testenden potentiellen Primteiler um einen Faktor 1/n.

Der Hauptgrund, warum man bei der Suche nach großen Primzahlen gerade Mersenne-Zahlen benutzt, ist aber, daß man für diese mit dem unten beschriebenen Lucas-Lehmer-Test einen effektiven Primzahltest zur Verfügung hat.

Lucas-Lehmer-Test

Nach dem Kleinen Satz von Fermat gilt für jede Primzahl N (und jede beliebige Zahl a), daß a^N-1-1 durch N teilbar ist.
(Während für alle kleineren natürlichen Zahlen a^m-1 nicht durch N teilbar ist.)
Im Umkehrschluß: wenn man für eine Zahl N durch Probieren irgendeine Zahl a findet, so daß a^N-1-1 nicht durch N teilbar ist, dann hat man bewiesen, daß N keine Primzahl ist (ohne daß man eine Zerlegung von N in Faktoren finden muß, was oft sehr aufwendig ist).

Dieser Satz hat auch eine Umkehrung: wenn es eine Zahl a gibt, so daß a^N-1-1 durch N teilbar ist, aber für alle Teiler m von N-1 a^m-1 nicht durch N teilbar ist, dann ist N eine Primzahl. Auf diesem Satz basiert das Lucas-Lehmer-Verfahren, von dem es verschiedene Varianten gibt.

Für viele Zahlen ist dieses Verfahren recht aufwendig, weil man ja erst alle Teiler von N-1 kennen muß. Für Mersenne-Zahlen M_n=2ⁿ-1 gibt es allerdings eine sehr effiziente Variante des Lucas-Lehmer-Verfahrens, deren Effizienz letztlich darauf beruht, daß die Binärdarstellung der Mersenne-Zahlen nur 1’en benutzt.
(Trotzdem braucht natürlich bei Zahlen in der Größenordnung der aktuellen Rekorde das Lucas-Lehmer-Verfahren mehrere Tage.)

Das Verfahren läuft wie folgt: man definiert eine Folge a_k rekursiv durch a₀=4, a_k+1=a_k²-2. Die Mersenne-Zahl M_n ist dann eine Primzahl genau dann, wenn a_n-2 durch M_n teilbar ist. (Beweis hier.)

Die Berechnung der Folge kann man vereinfachen, indem man immer modulo M_n rechnet. (Und eben dieses Restklassen-Rechnen wird wesentlich einfacher, wenn die Binärdarstellung der Basis nur 1’en enthält, d.h. für Mersenne-Zahlen.)
Die Komplexität dieses Algorithmus ist O(n² log(n) log(log(n))), deutlich besser als andere Algorithmen für Primzahl-Tests.

Verteiltes Rechnen

Die neuen Primzahlen (ebenso wie alle Primzahl-Rekorde der letzten 12 Jahre) wurden im GIMPS-Projekt gefunden. Dazu schreibe ich morgen einen eigenen Artikel.

Praktische Anwendungen: Wozu braucht man große Primzahlen?

So gut wie alle Bezahl-Verfahren im Internet benutzen RSA-Verschlüsselung. (Und zwar, ohne daß man dies als Nutzer überhaupt bemerkt. Wenn man online eine Bestellung aufgibt, etwa bei amazon, dann wird der Rechner des Kaufhauses automatisch die Verschlüsselung durchführen. Bereits während Sie die Daten in den Computer eingeben, noch bevor Ihre Daten überhaupt in die Datenleitung gelangen können.) Das RSA-Verfahren arbeitet mit Produkten großer Primzahlen. In der Praxis verwendet man etwa 100- bis 200-stellige Primzahlen, aber man muß sich natürlich darauf einstellen, in Zukunft auch größere Primzahlen zu benötigen.
Praktisch läuft das so, daß bei Verbindungsaufnahme der Kaufhaus-Rechner zwei große Primzahlen p,q nach einem Zufallsverfahren erzeugt, und das Produkt dieser beiden Zahlen pq an Ihren Rechner übermittelt. (Außerdem gibt es noch einen geheimen Schlüssel, der nur im Kaufhaus-Rechner gespeichert wird und einen öffentlichen Schlüssel, der über die Leitung an Ihren Rechner übertragen wird.) Das Produkt pq und der öffentliche Schlüssel (die beide über die evtl. unsicheren Leitungen übertragen worden sind), werden dann von Ihrem Rechner zur Verschlüsselung Ihrer Daten verwendet. Zur Entschlüsselung reichen diese Informationen aber nicht aus, dazu braucht man den geheimen Schlüssel, der beim Kaufhaus-Rechner gespeichert ist und nicht über die Leitung übertragen wurde.
Der Punkt ist, daß nur das Produkt pq und der öffentliche Schlüssel, nicht aber der geheime Schlüssel, über die unsichere Leitung übertragen wurde. Die Primzahlen p,q wurden im Kaufhaus-Rechner benutzt, um den geheimen Schlüssel zu berechnen, und anschließend ‘vernichtet’. Wer nur das Produkt pq über die unsichere Leitung abgehört hat, aber nicht p und q kennt, wird den geheimen Schlüssel nicht mit vernünftigem Aufwand berechnen können. (Wie das alles mathematisch funktioniert, kann man hier nachlesen.)
Jedenfalls möchte man natürlich bei jedem Kunden andere, zufällig erzeugte Primzahlen für die Verschlüsselung verwenden und deshalb braucht man einen großen Pool an großen Primzahlen.
Natürlich braucht man hier eher einen Pool an gleichgroßen Primzahlen und für heutige Zwecke reichen 100- bis 200-stellige Primzahlen völlig aus. So gesehen werden die neuen Rekord-Primzahlen also in den nächsten Jahren sicherlich noch nicht in Verschlüsselungsverfahren eingesetzt werden.

¹: Beweis (aus der Wikipedia): If p divides 2ⁿ − 1 then 2ⁿ ≡ 1 (mod p). By Fermat’s Little Theorem, 2^{p − 1} ≡ 1 (mod p). Assume there exists such a n which does not divide p − 1. Then as n and p − 1 must be relatively prime, a similar application of Fermat’s Little Theorem says that (p − 1)^{n − 1} ≡ 1 (mod n). Thus there is a number x ≡ (p − 1)^{n − 2} for which (p − 1)·x ≡ 1 (mod n), and therefore a number k for which (p − 1)·x − 1 = kn. Since 2^{p − 1} ≡ 1 (mod p), raising both sides of the congruence to the power x gives 2^{(p − 1)x} ≡ 1, and since 2ⁿ ≡ 1 (mod p), raising both sides of the congruence to the power k gives 2^kn ≡ 1. Thus 2^{(p − 1)x} ÷ 2^kn = 2^{(p − 1)x – kn} ≡ 1 (mod q). But by definition, (p − 1)x − kn = 1, implying that 2¹ ≡ 1 (mod p); in other words, that p divides 1. Thus the initial assumption that n does not divide p − 1 is untenable.

Nachtrag (15.9.): Es gibt inzwischen eine dpa-Meldung, die unter anderem in der Berliner Zeitung und Focus-online veröffentlicht wurde. Diese Meldung enthält mehrere Fehler:
– es trifft nicht zu, daß die beiden Zahlen unabhängig von Duell und Giltrap gefunden wurden. Die Namen der Entdecker sind von GIMPS bisher nicht bekanntgegeben worden (was möglicherweise mit dem ausgelobten Preisgeld für die erste Primzahl mit mehr als 10 Millionen Stellen zu tun hat). Von Duell und Giltrap stammen nur die ersten unabhängigen Bestätigungen der Primzahleigenschaft.
– es ist offensichtlicher Unsinn, daß man noch nicht weiß, welche der beiden Primzahlen die größere ist: für Mersenne-Zahlen ist natürlich M_n größer als M_m genau dann, wenn n größer als m ist, was man leicht überprüfen kann.
– es trifft nicht zu, daß ein endgültiges Ergebnis Anfang dieser Woche erwartet wird. Zwar war die Bestätigung der 2. Primzahl ursprünglich für den 14.9. avisiert, aber sie ging dann doch wesentlich schneller als erwartet (und als bei der 1. Zahl) und lag bereits Anfang letzter Woche vor. (Inzwischen gibt es noch eine 2. und für die erste Zahl auch eine 3. unabhängige Bestätigung.) Für Anfang dieser Woche ist lediglich eine Presseerklärung mit Bekanntgabe der Zahlen (die ja bisher noch geheimgehalten werden) geplant.
– Primzahlen sind nur durch sich selbst und durch 1 teilbar (nicht oder wie in der dpa-Meldung).
Sonst ist die dpa-Meldung aber richtig.

Nachtrag (17.9.): Wie George Szpiro in einem Kommentar auf Mathematik im Alltag schreibt, wurden die neuen Primzahlen bis Dienstag geheimgehalten, weil GIMPS ein Abkommen mit einer Zeitung in San Diego darüber hatte, daß die Informationen erst öffentlich gemacht werden darf, nachdem die Zeitung ihren Artikel publiziert hat.
Szpiro schreibt in einem Brief an die EFF: “[…] The practice of holding back mathematical results for the profit of a local newspaper is a very negative precedence. After all, the GIMPS project depends on the participation of volunteers from all over the world. The partisan information policy exhibited by Kurowski and Woltman makes a mockery of their good will. It is also counter to free speech, transparency, abuse of intellectual property rights – all principles the EFF stands and fights for. It is also against the most basic ideas of scientific openness and progress. […]”

Nactrag (2.10.): Eine sehr lesbare Darstellung zum Lucas-Lehmer-Test findet man in “What’s New”.