EINE 155-STELLIGE ZAHL AUF GRAFIKKARTEN ZERLEGT

Eine große Zahl in ihre Primfaktoren zu zerlegen, ist schwer, und diese Schwierigkeit ist für die Kryptografie wichtig – weshalb die Arbeit sorgfältig darlegt, was ihr Ergebnis nicht gefährdet. Öffentliche Zahlen der „RSA Challenge“ dienen als Maßstab für Faktorisierungsmethoden. RSA-155 ist eine davon: 155 Stellen, also 512 Bit.

Zwei Siebe, je ein Rekord

Zwei Familien von Algorithmen dominieren. Das Zahlkörpersieb (Number Field Sieve) ist der Champion für sehr große Zahlen: Es zerlegte RSA-155 schon 1999, und laut der Arbeit liegt der allgemeine Rekord inzwischen bei einer 270-stelligen Zahl, RSA-896, im Jahr 2026. Das ältere quadratische Sieb ist asymptotisch langsamer und nach den Worten der Autoren selbst „das falsche Werkzeug“ für allgemeine Rekorde. Es hat aber eine eigene Rekordliste: Die größte damit zerlegte Zahl war RSA-150 im Juni 2025, mit 11.664 CPU-Kernstunden.

Das quadratische Sieb sucht viele kleine Zahlen, die sich vollständig über eine Menge kleiner Primzahlen zerlegen lassen, und kombiniert sie dann mit linearer Algebra zu zwei Quadraten x² und y², die modulo N gleich sind. Ein größter gemeinsamer Teiler enthüllt dann einen Faktor. Auf einem Computer ist das ein Albtraum für Grafikprozessoren (GPUs): Speicherzugriffe streuen weit über jeden Cache hinaus, die Tests sind voller Verzweigungen, und die abschließende Algebra arbeitet in einer binären Arithmetik, die keine Herstellerbibliothek unterstützt. Frühere GPU-Ansätze beschleunigten nur einzelne Schritte.

Alles auf der Grafikkarte

Fabian Januszewski und Christoph Heinrichs vom Institut für Mathematik der Universität Paderborn haben CUDA-MPQS entwickelt, ein quelloffenes quadratisches Sieb, bei dem jede Stufe – Vorbereiten der Polynome, Sieben, Prüfen der Kandidaten, Zusammenführen von Teilergebnissen, Aufbau der Matrix, ihr Lösen und das Ziehen der abschließenden Quadratwurzel – auf der GPU läuft. Der gewöhnliche Prozessor orchestriert nur, richtet ein und übernimmt Ein- und Ausgabe; die wenigen verbleibenden Schritte auf dem Host listen die Autoren ausdrücklich auf. Bei einem 100-stelligen Test war die GPU 99,9 % der Siebzeit ausgelastet, ohne Pause zum Warten auf den Prozessor.

Das Hochskalieren deckte einen subtilen Fehler auf. Bei der Größe von RSA-155 lief ein beim Sieben verwendeter 8-Bit-Zähler ausgerechnet bei den wertvollsten Kandidaten über und verwarf stillschweigend 98 bis 99,5 % von ihnen. Das Team ersetzte ihn durch einen sättigenden Zähler, der nachweislich identische Ergebnisse liefert.

RSA-155 in etwa einem Tag

Am 14. Juli 2026 zerlegte die Pipeline RSA-155 in zwei Primzahlen mit je 78 Stellen, geprüft sowohl auf der GPU als auch auf dem Host:

• Sieben: 64 NVIDIA-H100-GPUs auf 16 Knoten, 10,8 Stunden, etwa 17,3 Millionen gesammelte Relationen.
• Lineare Algebra: eine einzige H100 für 10,9 Stunden, an einer Matrix mit 16,7 Millionen Zeilen und 684 Millionen Nicht-Null-Einträgen.
• Gesamt: 700,6 GPU-Stunden und 242 Kilowattstunden, rund 24 Stunden vom Start bis zu den Faktoren. Das Sieben machte 98,4 % des Aufwands aus.

Nach Wissen der Autoren ist dies die größte ganze Zahl, die je mit dem quadratischen Sieb faktorisiert wurde, fünf Stellen über dem bisherigen Rekord – und erreicht mit der einfachsten Variante der Methode, die nur eine „große Primzahl“ pro Relation behält, wo jüngere Rekorde drei verwendeten.

Schneller als die besten Prozessoren

Bei einer 100-stelligen Zahl ist eine einzige H100 in 29,2 Sekunden fertig, eine RTX 5070 Ti für Endverbraucher in 51 Sekunden. In einem kontrollierten Vergleich mit derselben Zahl, mit Energiemessung auf beiden Seiten, war eine H100 3,6- bis 4,2-mal schneller als das schnellste CPU-basierte quadratische Sieb auf 96 Kernen eines AMD-EPYC-Prozessors und etwa neun- bis zehnmal schneller als ein anderes Standardpaket. Außerdem faktorisierten sie RSA-150 erneut in 302,9 GPU-Stunden, gegenüber den 11.664 Kernstunden des bisherigen Rekords – ein Verhältnis, das nach Betonung der Autoren keine Beschleunigung unter gleichen Bedingungen darstellt.

Keine Gefahr für die Verschlüsselung

Die Autoren sind deutlich: RSA-155 war bereits faktorisiert, dies ist kein allgemeiner Faktorisierungsrekord, und „nichts hier verringert eine Sicherheitsmarge“. Der Code ist zudem bewusst auf etwa 155 Stellen begrenzt. Ihr Interesse liegt woanders: zu zeigen, dass ein unregelmäßiger, verzweigungsreicher Algorithmus vollständig auf einer GPU laufen kann. Als natürliches nächstes Ziel nennen sie den GPU-Gittersieber (Lattice Siever) im Herzen des Zahlkörpersiebs – eine Arbeit, die andere, wie sie anmerken, inzwischen begonnen haben, indem sie RSA-260 und RSA-896 mit GPU-Portierungen eines bestehenden Pakets faktorisierten, Letztere mit Claude erstellt.

Interessenkonflikt. Die Autoren geben an, dass generative KI und agentische Programmierwerkzeuge eingesetzt wurden: Anthropics Claude-Modelle (über Claude Code) zusammen mit OpenAIs GPT- und Googles Gemini-Modellen für die Softwareentwicklung sowie Claude-Modelle für die Aufbereitung der Daten und des Manuskripts. Sie erklären, dass alle KI-Ausgaben manuell geprüft und verifiziert wurden. Claude hat auch den vorliegenden Artikel geschrieben.