Ein PC an einer US-amerikanischen Universität hat die bislang größte bekannte Primzahl gefunden. Das Zahlenmonster hat 17,4 Millionen Stellen. Ausgedruckt auf Papier würde sie fast 6000 Seiten füllen.
Die Jäger von Rekord-Primzahlen vermelden einen neuen Treffer: Die Zahl 257.885.161 - 1 sei nur durch 1 und sich selbst teilbar und damit die größte bislang bekannte Primzahl, heißt es auf der Webseite des Projekts Gimps (Great Internet Mersenne Prime Search). Es handle sich um die größte bekannte Primzahl mit genau 17.425.170 Stellen. Würde man die Zahl auf Papier im A4-Format ausdrücken, benötigte man rund 5800 Seiten.
Entdeckt wurde die Rekord-Primzahl auf einem Computer von Curtis Coopers, einem Mathematiker von der University of Central Missouri in Warrensburg (USA). Coopers hat auf dem PC eine Software des Projekts Gimps installiert, die Zahlen der Form 2p-1 auf ihre Teiler untersucht. Primzahlen der Form 2p -1 nennt man Mersenne-Primzahlen. Es lässt sich leicht beweisen, dass 2p -1 nur dann eine Primzahl sein kann, wenn p selbst eine Primzahl ist.
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.
Computer 39 Tage beschäftigt
Bei dem nun entdeckten Zahlenmonster 257.885.161 -1 handelt es sich erst um die 48. bekannte Mersenne-Primzahl überhaupt. Coopers PC benötigte 39 Tage, um nachzuweisen, dass der Gigant mit 17,4 Millionen Stellen keine Teiler außer 1 und sich selbst hat. Für Cooper ist es bereits die dritte Mersenne-Primzahl, die ein Computer aus seinem Labor gefunden hat. Auch die Zahlen mit den Nummern 43 und 44 gehen auf sein Konto.
Ab der 35. Mersenne-Primzahl, entdeckt 1996, wurden alle bis dahin unbekannten Mersenne-Primzahlen mithilfe der Gimps-Software gefunden. Wer bei dem Projekt mitmacht, dessen Computer bekommt von einem Gimps-Server eine achtstellige Primzahl p zugeteilt. Das Programm berechnet dann die Zahl 2p - 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. Gimps funktioniert damit ganz ähnlich wie das Seti-Projekt, bei dem Freiwillige die Rechenpower ihres PCs für die Suche nach Signalen Außerirdischer im kosmischen Rauschen zur Verfügung stellen.
Wenn man Glück hat und mit Gimps eine neue Mersenne-Primzahl findet, kassiert man eine kleine Belohnung. Im Fall von Nummer 48 (257.885.161 - 1) waren dies 3000 US-Dollar. Für die Entdeckung der ersten Mersenne-Primzahl mit mehr als 10 Millionen Stellen wurden im Jahr 2008 sogar 100.000 Dollar gezahlt.
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 Online-Banking, nutzt die Tatsache aus, dass eine große Zahl nur mit extrem hohem Aufwand in ihre Primfaktoren zerlegt werden kann.
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 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.
Die nun gefundene 48. Mersenne-Primzahl eignet sich fürs Online-Banking freilich nicht. Dafür ist sie viel zu groß. Bei RSA kommen üblicherweise Primzahlen mit mehreren hundert Stellen zum Einsatz und nicht mit 17,4 Millionen.
Keine Kommentare:
Kommentar veröffentlichen