GPU-Accelerated Graph-Colored Simulated Annealing for Integer Factorization

De beveiliging van een groot deel van de moderne digitale wereld rust op een eenvoudige wiskundige truc: het is ongelooflijk gemakkelijk om twee grote priemgetallen met elkaar te vermenigvuldigen, maar het is moeilijk om te achterhalen welke twee getallen werden gebruikt door enkel naar het resultaat te kijken. Deze eenrichtingsweg vormt de basis van RSA-encryptie, het systeem dat online bankieren, privéberichten en veilige communicatie beschermt. Decennialang was de enige bekende manier om deze code te kraken het proberen van elke mogelijke combinatie van getallen totdat het juiste paar werd gevonden, een taak die zo omvangrijk is dat zelfs de krachtigste supercomputers langer zouden doen onderzoeken voor grote sleutels dan de leeftijd van het universum. Hoewel quantumcomputers beloven op een dag deze code direct te kunnen kraken, zijn ze nog niet klaar voor de klus. Dit laat een gat open waar klassieke computers een nieuwe manier moeten vinden om het probleem op te lossen, niet door brute kracht, maar door de zoektocht naar de ontbrekende getallen te behandelen als een puzzel van energie en balans.

Onderzoekers aan het Indian Institute of Technology Madras hebben een nieuwe methode ontwikkeld om deze uitdaging aan te pakken met behulp van een standaard graphics processing unit, het soort chip dat in high-end computers voor gaming en videorendering wordt gevonden. In plaats van de getallen direct te proberen te raden, transformeerden zij het probleem in een landschap van heuvels en dalen, waarbij de oplossing zich bevindt in het diepste punt van het diepste dal. Ze brachten de bits van de twee verborgen priemgetallen in kaart op een rooster van minuscule schakelaars, waarvan elke zich in één van de twee staten kan bevinden. Het doel was om de specifieke arrangement van deze schakelaars te vinden die de laagst mogelijke energietoestand creëert, een configuratie die wiskundig gezien de twee juiste priemfactoren codeert.

Om dit op te lossen, gebruikte het team een techniek genaamd simulated annealing, die het fysieke proces van het afkoelen van metaal nabootst om defecten te verwijderen. In hun digitale versie begint het systeem met een willekeurige arrangement van schakelaars en een hoog niveau van "hitte", waardoor de schakelaars vrij kunnen flippen. Terwijl het systeem afkoelt, settelen de schakelaars in een stabieler patroon. De onderzoekers ontwierpen hun software om te draaien op een enkele krachtige graphics chip, de NVIDIA GH200, die duizenden berekeningen tegelijkertijd kan uitvoeren. Omdat de wiskundige kaart die zij creëerden grotendeels leeg is — wat betekent dat de meeste schakelaars niet met elkaar interageren — organiseerden zij de taken zodanig dat de computer zich alleen concentreerde op de verbindingen die daadwerkelijk bestonden. Dit stelde hen in staat om veel schakelaars gelijktijdig bij te werken zonder fouten te veroorzaken, een prestatie die een slimme sorteermethode vereiste om te garanderen dat niet twee interagerende schakelaars op exact hetzelfde moment werden gewijzigd.

Het systeem vond niet altijd direct het perfecte antwoord. In hun tests kwam de annealer consequent heel dicht bij de juiste oplossing, vaak binnen een paar procent van de werkelijke getallen. Om deze laatste kloof te overbruggen, voegden de onderzoekers een tweede stap toe: een geleide zoektocht die getallen controleerde in de buurt van de beste gok van de computer. Ze gebruikten een filtermethode om getallen over te slaan die onmogelijk priem konden zijn, wat de benodigde hoeveelheid werk drastisch verminderde. Voor een 100-bit getal duurde het hele proces, van de initiële setup tot het vinden van de uiteindelijke factoren, slechts iets meer dan zes minuten op één machine. Dit is aanzienlijk sneller dan traditionele methoden, die voor dezelfde taak uren zouden nodig hebben.

De onderzoekers testten hun pipeline op getallen variërend van 16 tot 128 bits. Hoewel ze erin slaagden 100-bit getallen binnen enkele minuten te factoriseren, merkten ze op dat de methode nog steeds vertrouwt op een laatste zoekstap om het exacte antwoord te vinden. De snelheid van deze laatste stap hangt sterk af van hoe dicht de initiële gok bij de waarheid ligt. Het team kwam tot de conclusie dat hun methode consequent een veel beter startpunt bood dan oudere, simpelere gokken, wat de tijd die nodig was voor de laatste zoektocht met een grote marge verminderde. Ze demonstreerden ook dat het gebruik van een specifieke wiskundige techniek, bekend als Coppersmith's methode, het proces voor grotere getallen verder zou kunnen versnellen, wat de tijd potentieel zou kunnen verkorten van maanden naar dagen voor 128-bit getallen.

Dit werk breekt de huidige encryptiestandaarden niet, aangezien de getallen die getest zijn veel kleiner zijn dan de getallen die gebruikt worden in de echte wereld van beveiliging, die doorgaans honderden cijfers bevatten. Het bewijst echter dat een klassieke computer, wanneer deze wordt geleid door de juiste wiskundige structuur en geoptimaliseerd voor parallelle verwerking, dit type probleem veel efficiënter kan oplossen dan voorheen gedacht. De studie suggereert dat de bottleneck niet langer de ruwe snelheid van de computer is, maar eerder hoe goed de initiële gok kan worden verfijnd. Als toekomstige verbeteringen de computer nog dichter bij de oplossing kunnen krijgen, zou de laatste zoekstap zo klein kunnen worden dat het hele proces op een dag in polynomiale tijd zou kunnen draaien, een theoretische snelheid die het landschap van de cryptografie zou veranderen. Voor nu hebben de onderzoekers aangetoond dat door de unieke vorm van het probleem te respecteren en de enorme parallelle kracht van moderne graphics chips te gebruiken, het mogelijk is om een schijnbaar onmogelijke wiskundige slot in een oplosbare puzzel te veranderen.