GPU-Accelerated Graph-Colored Simulated Annealing for Integer Factorization

Die Sicherheit eines Großteils der modernen digitalen Welt beruht auf einem einfachen mathematischen Trick: Es ist unglaublich einfach, zwei große Primzahlen miteinander zu multiplizieren, aber es ist schwer herauszufinden, welche zwei Zahlen verwendet wurden, wenn man nur das Ergebnis betrachtet. Diese Einbahnstraße ist das Fundament der RSA-Verschlüsselung, des Systems, das Online-Banking, private Nachrichten und sichere Kommunikation schützt. Jahrzehntelang war der einzige bekannte Weg, diesen Code zu knacken, darin bestand, jede mögliche Zahlenkombination auszuprobieren, bis das richtige Paar gefunden wurde – eine Aufgabe, die so gewaltig ist, dass selbst die leistungsstärksten Supercomputer länger als das Alter des Universums bräuchten, um sie für große Schlüssel zu lösen. Während Quantencomputer versprechen, diesen Code eines Tages sofort zu knacken, sind sie noch nicht bereit für diese Aufgabe. Dies hinterlässt eine Lücke, in der klassische Computer einen neuen Weg finden müssen, um das Problem zu lösen – nicht durch Brute Force, sondern indem sie die Suche nach den fehlenden Zahlen als ein Rätsel aus Energie und Gleichgewicht behandeln.

Forscher am Indian Institute of Technology Madras haben eine neue Methode entwickelt, um diese Herausforderung mit einer Standard-Grafikverarbeitungseinheit anzugehen, dem Typ Chip, der in High-End-Computern für Gaming und Videorendering zu finden ist. Anstatt zu versuchen, die Zahlen direkt zu erraten, transformierten sie das Problem in eine Landschaft aus Hügeln und Tälern, in der die Lösung ganz unten im tiefsten Tal liegt. Sie bildeten die Bits der zwei verborgenen Primzahlen auf ein Gitter aus winzigen Schaltern ab, von denen jeder sich in einem von zwei Zuständen befinden kann. Das Ziel war es, die spezifische Anordnung dieser Schalter zu finden, die den niedrigstmöglichen Energiezustand erzeugt – eine Konfiguration, die die beiden korrekten Primfaktoren mathematisch kodiert.

Um dies zu lösen, nutzte das Team eine Technik namens Simulated Annealing, die den physikalischen Prozess des Abkühlens von Metall nachbessimt, um Defekte zu entfernen. In ihrer digitalen Version beginnt das System mit einer zufälligen Anordnung von Schaltern und einem hohen Grad an „Hitze“, was es den Schaltern ermöglicht, frei zu springen. Während das System abkühlt, pendeln sich die Schalter in ein stabileres Muster ein. Die Forscher gestalteten ihre Software so, dass sie auf einem einzigen leistungsstarken Grafikchip, dem NVIDIA GH200, läuft, der tausende Berechnungen gleichzeitig durchführen kann. Da die von ihnen erstellte mathematische Karte größtenteils leer ist – was bedeutet, dass die meisten Schalter nicht miteinander interagieren – organisierten sie die Arbeit so, dass sich der Computer nur auf die tatsächlich existierenden Verbindungen konzentriert. Dies ermöglichte es ihnen, viele Schalter gleichzeitig zu aktualisieren, ohne Fehler zu verursachen, eine Leistung, die ein kluges Sortierverfahren erforderte, um sicherzustellen, dass nicht zwei interagierende Schalter im exakt selben Moment geändert werden.

Das System fand nicht immer sofort die perfekte Antwort. In ihren Tests landete der Annealer konsistent sehr nah an der korrekten Lösung und kam oft innerhalb weniger Prozent an die wahren Zahlen heran. Um diese letzte Lücke zu schließen, fügten die Forscher einen zweiten Schritt hinzu: eine geführte Suche, die Zahlen in der Nähe der besten Vermutung des Computers überprüfte. Sie verwendeten eine Filtermethode, um Zahlen zu überspringen, die unmöglich prim sein konnten, was die erforderliche Arbeit drastisch reduzierte. Für eine 100-Bit-Zahl dauerte der gesamte Prozess, von der initialen Einrichtung bis zum Finden der endgültigen Faktoren, etwas mehr als sechs Minuten auf einer einzigen Maschine. Dies ist signifikant schneller als traditionelle Methoden, die für dieselbe Aufgabe Stunden benötigen würden.

Die Forscher testeten ihre Pipeline an Zahlen im Bereich von 16 bis 128 Bit. Während sie 100-Bit-Zahlen in wenigen Minuten erfolgreich faktorisierten, merkten sie an, dass die Methode immer noch auf einen finalen Suchschritt angewiesen ist, um die exakte Antwort zu finden. Die Geschwindigkeit dieses letzten Schritts hängt stark davon ab, wie nah die erste Vermutung an der Wahrheit liegt. Das Team stellte fest, dass ihre Methode konsistent einen viel besseren Ausgangspunkt lieferte als ältere, simplere Vermutungen, was die Zeit für die finale Suche erheblich verkürzte. Sie demonstrierten auch, dass die Verwendung einer spezifischen mathematischen Technik, bekannt als Coppersmith-Methode, den Prozess für größere Zahlen weiter beschleunigen könnte, was die Zeit für 128-Bit-Zahlen potenziell von Monaten auf Tage reduzieren würde.

Diese Arbeit knackt die aktuellen Verschlüsselungsstandards nicht, da die getesteten Zahlen weit kleiner sind als die, die in der realen Sicherheit verwendet werden, welche typischerweise Zahlen mit hunderten von Stellen beinhalten. Sie beweist jedoch, dass ein klassischer Computer, wenn er durch die richtige mathematische Struktur geleitet und für die parallele Verarbeitung optimiert wird, diese Art von Problem wesentlich effizienter lösen kann als bisher angenommen. Die Studie legt nahe, dass der Engpass nicht mehr die reine Geschwindigkeit des Computers ist, sondern vielmehr, wie gut die erste Vermutung verfeinert werden kann. Wenn zukünftige Verbesserungen es schaffen, den Computer noch näher an die Lösung zu bringen, könnte der finale Suchschritt so klein werden, dass der gesamte Prozess eines Tages in polynomieller Zeit ablaufen könnte – eine theoretische Geschwindigkeit, die die Landschaft der Kryptografie verändern würde. Für den Moment haben die Forscher gezeigt, dass es möglich ist, indem man die einzigartige Form des Problems respektiert und die massive parallele Kraft moderner Grafikchips nutzt, ein scheinbar unlösbares mathematisches Schloss in ein lösbares Rätsel zu verwandeln.