GPU-Accelerated Graph-Colored Simulated Annealing for Integer Factorization

La sicurezza di gran parte del mondo digitale moderno si basa su un semplice trucco matematico: è incredibilmente facile moltiplicare due grandi numeri primi tra loro, ma è difficile capire quali due numeri siano stati utilizzati guardando semplicemente il risultato. Questa strada a senso unico è la base della crittografia RSA, il sistema che protegge l'online banking, i messi privati e le comunicazioni sicure. Per decenni, l'unico modo noto per rompere questo codice è stato provare ogni possibile combinazione di numeri finché non si trovava la coppia corretta, un compito così vasto che anche i supercomputer più potenti impiegherebbero più tempo dell'età dell'universo per risolvere il problema per chiavi di grandi dimensioni. Sebbene i computer quantistici promettano di poter un giorno violare questo codice istantaneamente, non sono ancora pronti per il compito. Ciò lascia un vuoto in cui i computer classici devono trovare un nuovo modo per risolvere il problema, non tramite la forza bruta, ma trattando la ricerca dei numeri mancanti come un puzzle di energia e di equilibrio.

I ricercatori dell'Indian Institute of Technology Madras hanno sviluppato un nuovo metodo per affrontare questa sfida utilizzando una normale unità di elaborazione grafica, il tipo di chip presente nei computer di fascia alta per il gaming e il rendering video. Invece di cercare di indovinare direttamente i numeri, hanno trasformato il problema in un paesaggio di colline e valli, dove la soluzione risiede proprio sul fondo della valle più profonda. Hanno mappato i bit dei due numeri primi nascosti su una griglia di piccoli interruttori, ciascuno dei quali può trovarsi in uno di due stati. L'obiettivo era trovare la specifica disposizione di questi interruttori che crea lo stato di energia più basso, una configurazione che codifica matematicamente i due fattori primi corretti.

Per risolvere questo, il team ha utilizzato una tecnica chiamata annealing simulato (ricottura simulata), che imita il processo fisico del raffreddamento dei metalli per rimuovere i difetti. Nella loro versione digitale, il sistema parte da una disposizione casuale di interruttori e da un alto livello di "calore", permettendo agli interruttori di scattare liberamente. Man mano che il sistema si raffredda, gli interruttori si assestano in un modello più stabile. I ricercatori hanno progettato il loro software per essere eseguito su un singolo chip grafico potente, l'NVIDIA GH200, che può eseguire migliaiz di calcoli contemporaneamente. Poiché la mappa matematica che hanno creato è per lo più vuota — il che significa che la maggior parte degli interruttori non interagisce tra di sé — hanno organizzato il lavoro in modo che il computer si concentrasse solo sulle connessioni effettivamente esistenti. Ciò ha permesso loro di aggiornare molti interruttori simultaneamente senza causare errori, un'impresa che ha richiesto un metodo di ordinamento intelligente per garantire che nessun paio di interruttori interagenti venisse modificato nello stesso istante.

Il sistema non sempre trovava la risposta perfetta immediatamente. Nei loro test, l'annealer arrivava costantemente molto vicino alla soluzione corretta, spesso entro pochi punti percentuali dai numeri reali. Per colmare questo ultimo divario, i ricercatori hanno aggiunto un secondo passaggio: una ricerca guidata che controllava i numeri vicini al miglior tentativo del computer. Hanno utilizzato un metodo di filtraggio per saltare i numeri che non potevano possibilmente essere primi, riducendo drasticamente il lavoro richiesto. Per un numero di 100 bit, l'intero processo, dalla configurazione iniziale alla ricerca dei fattori finali, ha richiesto poco più di sei minuti su una singola macchina. Questo è significativamente più veloce dei metodi tradizionali, che richiederebbero ore per lo stesso compito.

I ricercatori hanno testato la loro pipeline su numeri che vanno da 16 a 128 bit. Sebbene abbiano fattorizzato con successo numeri di 100 bit in pochi minuti, hanno notato che il metodo si affida ancora a un passaggio di ricerca finale per trovare la risposta esatta. La velocità di questo passaggio finale dipende fortemente da quanto sia vicino il tentativo iniziale alla verità. Il team ha scoperto che il loro metodo forniva costantemente un punto di partenza molto migliore rispetto ai tentativi iniziali più semplici, riducendo il tempo necessario per la ricerca finale di un margine considerevole. Hanno anche dimostrato che l'uso di una tecnica matematica specifica nota come metodo di Coppersmith potrebbe accelerare ulteriormente il processo per numeri più grandi, potenzialmente riducendo il tempo da mesi a giorni per i numeri a 128 bit.

Questo lavoro non rompe gli attuali standard di crittografia, poiché i numeri testati sono molto più piccoli di quelli utilizzati nella sicurezza del mondo reale, che tipicamente coinvolgono numeri con centinaia di cifre. Tuttavia, dimostra che un computer classico, quando guidato dalla giusta struttura matematica e ottimizzato per l'elaborazione parallela, può risolvere questo tipo di problema in modo molto più efficiente di quanto precedentemente pensato. Lo studio suggerisce che il collo di bottiglia non è più la velocità pura del computer, ma piuttosto quanto bene possa essere raffinato il tentativo iniziale. Se i futuri miglioramenti riusciranno a portare il computer ancora più vicino alla soluzione, il passaggio di ricerca finale potrebbe diventare così piccolo che l'intero processo potrebbe un giorno girare in tempo polinomiale, una velocità teorica che cambierebbe il panorama della crittografia. Per ora, i ricercatori hanno dimostrato che, rispettando la forma unica del problema e utilizzando l'enorme potenza parallela dei moderni chip grafici, è possibile trasformare una serratura matematica apparentemente impossibile in un puzzle risolvibile.