23,2 Millionen Stellen Elektroingenieur entdeckt Rekordprimzahl

Ein Ingenieur aus Tennessee hat die größte bislang bekannte Primzahl aufgespürt. Sechs Tage brauchte sein Computer, um zu beweisen, dass der Zahlengigant mit 23 Millionen Stellen keine anderen Teiler hat als 1 und sich selbst.

Erste Stellen der 50. Mersenne-Primzahl
SPIEGEL ONLINE

Erste Stellen der 50. Mersenne-Primzahl


Die neue Rekordzahl beginnt mit der Ziffer 4. Dann folgen eine 6, eine 7 und mehr als 23 Millionen weitere Ziffern. Das Zahlenmonster ist die größte bekannte Primzahl, wie das Primzahlen-Forschungsprojekt "Great Internet Mersenne Prime Search" (Gimps) auf seiner Webseite berichtet. Wollte man die Zahl auf Papier der Größe A4 ausdrucken, bräuchte man knapp 8000 Seiten.

Entdeckt hat die Zahl Jonathan Pace, ein 51-jähriger Elektroingenieur aus Germantown im US-Bundesstaat Tennessee. Er hatte auf seinem Computer die Software Gimps Prime95 installiert, mit der jeder Computerbesitzer weltweit sich an der Jagd nach Primzahlen beteiligen kann. Man muss dafür nur eigene Rechnerkapazität zur Verfügung stellen. Pace macht dies nach Angaben des Gimps-Projekts bereits seit 14 Jahren. Für die Entdeckung der Rekordprimzahl kassiert er eine Prämie von 3000 Dollar.

Bei der entdeckten Zahl handelt es sich um eine besondere Primzahl - eine sogenannte Mersenne-Primzahl. Diese lässt sich in der Form 2p -1 schreiben, wobei p auch eine Primzahl ist. Es lässt sich relativ leicht zeigen, dass 2p -1 nur dann eine Primzahl sein kann, wenn p selbst eine Primzahl ist - hier geht es zum Beweis.

Berechnung dauerte sechs Tage

Die Software des Projekts Gimps teilt Freiwilligen auf der ganzen Welt bekannte große Primzahlen zu. Beim Ingenieur Pace war es die Primzahl 77.232.917. Die Software untersuchte dann, ob 277,232,917-1 ebenfalls eine Primzahl ist - also nur die Teiler 1 und sich selbst besitzt. Der Rechner des Ingenieurs meldete am 26. Dezember nach sechs Tagen Berechnung: Ja, das ist eine Primzahl. Vor der Bestätigung durch das Gimps-Projekt wurde die Prüfung auf vier weiteren Computern wiederholt.

Der Fund von Pace ist ein besonderer, denn es handelt sich um die 50. Mersenne-Primzahl. Bis zum 16. Jahrhundert glaubten Mathematiker, dass alle natürlichen Zahlen der Form 2p-1 Primzahlen sind, solange p selbst eine Primzahl ist. 1536 aber stellte ein Gelehrter fest, dass das nicht stimmt. 211 -1 = 2047 ist nämlich das Produkt von 23 und 89.

Der französische Mönch Marin Mersenne glaubte 1644, alle Primzahlen der Form 2p -1 für Primzahlen p<257 gefunden zu haben. Laut seinem Werk "Cogitata Physica-Mathematica" sollten dies p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 und 257 sein. Aber Mersenne irrte sich. 267 -1 und 2257 -1 erwiesen sich später nicht als Primzahlen. Dafür fehlten in Mersennes Liste noch die Zahlen p = 61, 89 und 107.

Mönch Marin Mersenne
imago/ Leemage

Mönch Marin Mersenne

Die ersten Mersenne-Primzahlen konnten noch mit Stift und Papier gefunden werden - heutzutage geht nichts mehr ohne Computer. Seit Ende 1996 wurden 16 neue Mersenne-Primzahlen entdeckt - stets mithilfe der Software Gimps Prime95. Die 48. Zahl mit 17,4 Millionen Stellen wurde 2013 bekannt gegeben, die 49. im Jahr 2016. Sie hat 22,3 Millionen Ziffern, knapp eine Million weniger als die nun bekannte Mersenne-Primzahl Nummer 50.

Primzahlen faszinieren Menschen seit Jahrtausenden - eine echte Anwendung gibt es aber erst, seit leistungsfähige Computer verfügbar sind. Mit Primzahlen werden Daten verschlüsselt - etwa bei der sicheren Kommunikation im Internet. Das sogenannte RSA-Verfahren, beispielsweise genutzt beim Onlinebanking, nutzt die Tatsache aus, dass eine große Zahl nur mit extrem hohem Aufwand in ihre Primfaktoren zerlegt werden kann.

Anwendung in Kryptografie

Die RSA-Verschlüsselung ist nicht kompliziert: Die Bank multipliziert zwei große 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. 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 Kryptografie 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.

Die in den vergangenen Jahren entdeckten Mersenne-Primzahlen eignen sich fürs Onlinebanking freilich nicht. Dafür sind sie viel zu groß. Bei RSA kommen üblicherweise Primzahlen mit mehreren Hundert Stellen zum Einsatz und nicht mit 23 Millionen.

hda

insgesamt 27 Beiträge
Alle Kommentare öffnen
Seite 1
rumloler 05.01.2018
1. citizen science
Jeder kann sich an solchen Projekten beteiligen indem man die Software BOINC auf seinem Computer oder Android Smartphone installiert. Über BOINC wird man Teil eines weltweiten Supercomputers und kann Projekte unterstützen die zum Beispiel auch Medikamente für Krebs, HIV oder Alzheimer suchen, Klimamodelle berechnen oder Projekte für Astronomie usw. Läuft auf meinem Computer und Smartphone seit Jahren, kann ich sehr empfehlen.
Ringmodulation 05.01.2018
2. Echte Anwendungen ohne Computer
Die Natur kennt Anwendungen von Primzahlen schon länger als sie den Menschen kennt. Stichwort Primzahlzyklus. Und da Spiegel Online doch in letzter Zeit gern mit neuen Formaten experimentiert: Warum nicht eine kleine Web-App, die die Zahl auf dem Bildschirm ausgibt? (Ja, ich weiß, das klicken dann wieder alle an und irgendwer errechnet dann, dass das die Temperatur des Planeten um 1/(2^p-1) Grad Celsius erhöht. Um wieviel Grad Celsius erhöht eigentlich die Mersennezahlen-Suche die Erdtemperatur?)
permissiveactionlink 05.01.2018
3. Sehr schön.
Und Dank Euklid wissen wir dann auch, dass die z.Z.größte vollkommene Zahl (das ist eine Zahl, die identisch ist mit der Summe ihrer echten Teiler, z.B. 6=1+2+3) der Zahl 2^154.465.833 + 2^77.232.916 entspricht. Denn V = 2^(p-1) * (2^p -1), wobei die Zahl in der 2.Klammer eine Mersenne-Primzahl ist.
permissiveactionlink 05.01.2018
4. #2, Ringmodulation
Mit dem Primzahlzyklus meinen Sie sicher das Auftreten bestimmter Zikadenarten in Nordamerika, die in Jahresabständen aus dem Boden krabbeln, die alle prim sind. Deshalb sind die Erscheinungsjahre alle relativ prim zueinander, sodass sich die Zikadenarten nur selten gegenseitig stören. Aber Primzahlen (alle !) sind auch in jedem Kreis zu finden, denn es gilt die wunderschöne Formel : Produkt von n=2 bis unendlich des Termes pn^2/(pn^2 -1) = pi^2/6. Für pn werden beginnend mit 2 nacheinander alle unendlich vielen Primzahlen in den Term eingesetzt und aufmultipliziert. Und das ergibt nach unendlich vielen Multiplikationen ein Sechstel des Quadrates von pi. PS : Für Computer und Smartphones gibt es kostenlose Rechenprogramme für beliebig große Zahlen. Damit kann man auch 2^77.232.917 - 1 berechnen und falls erwünscht, ausdrucken.
Don Lucio 05.01.2018
5. Nur 6 Tage?
Ein Privatmann knackt die höchste heute bekannte Primzahl in nur 6 Tagen. Mit welchem Equipment? Ich gehe mal davon aus, dass Geheimdienste und professionelle Hackerbanden über deutlich leistungsfähigere Rechenanlagen verfügen (PC, Graphikkarten) als dieser Ingenieur. Daraus würde dann folgen, dass das Knacken von nur erheblich niedrigwertigeren Primzahlen, wie sie Banken verwenden (lt. Artikel mit p=einige Hundert statt 23 Mio.) für professionelle Angreifer in nur Minuten möglich sein müsste. Um das zu beurteilen, müßte man wissen, mit welchem Gerät der Mr. Pace seine Zahl ermittelt hat. Kann das die SPON-Redaktion vielleicht noch nachliefern?
Alle Kommentare öffnen
Seite 1

© SPIEGEL ONLINE 2018
Alle Rechte vorbehalten
Vervielfältigung nur mit Genehmigung der SPIEGELnet GmbH


TOP
Die Homepage wurde aktualisiert. Jetzt aufrufen.
Hinweis nicht mehr anzeigen.