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.
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.
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