Neuer Weltrekord bei der Primfaktor-Zerlegung

Mathematikern der Universität Bonn ist es nach eigenenen Angaben gelungen, eine Zahl mit 158 Stellen in ihre Primfaktoren zu zerlegen. Die Wissenschaftler haben damit einen neuen Weltrekord aufgestellt -- bisher lag der Rekord aus dem Jahr 1999 bei 155 Stellen (512 Bit). Bei ihren Berechnungen verwendeten die Forscher den Linux-Cluster Parnass2, der aus 144 PCs mit 400-MHz-Pentium-II-Prozessoren besteht.

Jede ganze Zahl lässt sich als eindeutiges Produkt von Primzahlen darstellen -- eine Eigenschaft, die neben Mathematikern besonders Kryptographen interessiert. Viele der derzeit eingesetzten Codierungs-Verfahren wie RSA stützen sich auf die Tatsache, dass es sehr aufwendig ist, große Zahlen in ihre Primfaktoren zu zerlegen. Sollte es gelingen, auch große Zahlen mit realistischem Zeitaufwand in ihre Primfaktoren zu zerlegen, wäre ein Großteil der heutzutage eingesetzten Verschlüselungsverfahren angreifbar.

Der bisherige Rekord stammt aus dem Jahr 1999, in dem es einem internationalen Wissenschaftler-Team des niederländischen Forschungsinstitut für Mathematik und Computerwissenschaften in Amsterdam (CWI) gelungen war, eine 155-stellige Zahl zu zerlegen -- auch praktisch eine relevante Schranke: Damalige Verschlüsselungen basierten meist auf 512-stelligen Binärzahlen; 512 Binärstellen entsprechen aber 155 Stellen im Dezimalsystem.

Die heute eingesetzten Codierungs-Verfahren basieren in der Regel auf weit größeren Zahlen -- üblich sind 1024 Bit und mehr. "Sie sind durch unseren Rekord nicht gefährdet", erklärt Professor Jens Franke vom Bonner Institut für Mathematik, der zusammen mit Thorsten Kleinjung und Friedrich Bahr das Zahlenungetüm geknackt hat. Dennoch planen die Bonner Wissenschaftler gemeinsam mit ihren Kollegen vom CWI, die nächste Grenze zu überwinden und sich am RSA-Wettbewerb zu beteiligen: Für die Primfaktorzerlegung der Zahl RSA-576 (eine Zahl mit 174 Dezimalstellen) sind 10.000 US-Dollar Preisgeld ausgeschrieben. (wst)