Primzahlenrekord mit Linux-Rechnern

Mathematikern der Universität Bonn ist es nach eigenen Angaben gelungen, eine Zahl mit 158 Stellen in ihre Primfaktoren zu zerlegen, das sei neuer Weltrekord. Bei dem Versuch kamen keine Supercomputer, sondern handelsübliche Rechner mit Linux zum Einsatz.

Der bisherige Rekord stammt aus dem Jahr 1999. Damals gelang es einem internationalen Wissenschaftlerteam, eine 155-stellige Zahl zu zerlegen. Das sei auch praktisch eine relevante Schranke gewesen, teilten die Bonner-Mathematiker mit: Damalige Verschlüsselungen basierten meist auf 512-stelligen Binärzahlen; 512 Binärstellen entsprechen aber 155 Stellen im Dezimalsystem.

Zahlreiche Verschlüsselungsverfahren beruhen auf einer mathematischen Asymmetrie: Die Multiplikation von zwei Zahlen benötigt kaum Rechenzeit. Die Zerlegung einer Zahl in ihre Teiler ist um viele Größenordnungen aufwendiger. Heute eingesetzte Codierungsverfahren verwenden in der Regel Schlüssel mit über 512 Bit. "Sie sind durch unseren Rekord nicht gefährdet", erklärt Professor Dr. Jens Franke vom Institut für Mathematik an der Universität Bonn, der zusammen mit Dr. Thorsten Kleinjung und Friedrich Bahr die 158 Stellen geknackt hat.

Um große Zahlen in Primfaktoren zu zerlegen, werden in der Regel Supercomputer eingesetzt. "Unser Rekord ist der erste dieser Art, bei dem ein Netzwerk handelsüblicher Linux-Rechner zum Einsatz kam", so Professor Franke. Jeder Einzelcomputer arbeitete dabei parallel an der Lösung eines Teilaspektes.

"Solche parallelisierten Programme sind selbst für sehr viel größere Projekte einsetzbar", erklärt der Mathematiker. Gerade in der Endphase müssen die einzelnen Rechner ihre Ergebnisse extrem schnell miteinander abgleichen und neue Teilaufgaben verteilen. Zur Lösung dieser Aufgabe hatten die Mathematiker auf das Know-how der Bonner Abteilung für wissenschaftliches Rechnen und numerische Simulation zurückgegriffen.

Zusätzliche Informationen finden Sie in den Kryptographie-Grundlagen. (uba)