GPU-Accelerated Graph-Colored Simulated Annealing for Integer Factorization

La sécurité d'une grande partie du monde numérique moderne repose sur une simple astuce mathématique : il est incroyablement facile de multiplier deux grands nombres premiers entre eux, mais il est difficile de déterminer quels deux nombres ont été utilisés en regardant simplement le résultat. Cette rue à sens unique est le fondement du chiffrement RSA, le système qui protège les services bancaires en ligne, les messages privés et les communications sécurisées. Pendant des décennies, la seule façon connue de briser ce code était d'essayer toutes les combinaisons possibles de nombres jusqu'à ce que la paire correcte soit trouvée, une tâche si vaste que même les superordinateurs les plus puissants mettraient plus longtemps que l'âge de l'univers pour résoudre le problème pour de grandes clés. Bien que les ordinateurs quantiques promettent de pouvoir un jour briser ce code instantanément, ils ne sont pas encore prêts pour la tâche. Cela laisse un vide où les ordinateurs classiques doivent trouver une nouvelle façon de résoudre le problème, non pas par force brute, mais en traitant la recherche des nombres manquants comme un puzzle d'énergie et d'équilibre.

Des chercheurs de l'Institut indien de technologie de Madras ont développé une nouvelle méthode pour relever ce défi en utilisant un processeur graphique standard, le type de puce que l'on trouve dans les ordinateurs haut de gamme pour le jeu vidéo et le rendu vidéo. Au lieu d'essayer de deviner les nombres directement, ils ont transformé le problème en un paysage de collines et de vallées, où la solution se trouve tout au fond de la vallée la plus profonde. Ils ont projeté les bits des deux nombres premiers cachés sur une grille de minuscules commutateurs, chacun pouvant être dans l'un des deux états. L'objectif était de trouver l'arrangement spécifique de ces commutateurs qui crée l'état d'énergie le plus bas, une configuration qui encode mathématiquement les deux facteurs premiers corrects.

Pour résoudre cela, l'équipe a utilisé une technique appelée recuit simulé, qui imite le processus physique du refroidissement du métal pour éliminer les défauts. Dans leur version numérique, le système commence avec un arrangement aléatoire de commutateurs et un niveau élevé de « chaleur », permettant aux commutateurs de basculer librement. À mesure que le système refroidit, les commutateurs se stabilisent dans un motif plus stable. Les chercheurs ont conçu leur logiciel pour qu'il s'exécute sur une seule puce graphique puissante, la NVIDIA GH200, qui peut effectuer des milliers de calculs simultanément. Comme la carte mathématique qu'ils ont créée est principalement vide — ce qui signifie que la plupart des commutateurs n'interagissent pas entre eux — ils ont organisé le travail de sorte que l'ordinateur ne se concentre que sur les connexions qui existent réellement. Cela a permis de mettre à jour de nombreux commutateurs simultanément sans provoquer d'erreurs, un exploit qui a nécessité une méthode de tri ingénieuse pour garantir qu'aucun de deux commutateurs interagissant ne soit modifié au même moment.

Le système ne trouvait pas toujours la réponse parfaite immédiatement. Lors de leurs tests, le recuiseur arrivait systématiquement très près de la solution correcte, se rapprochant souvent de quelques pour cent des nombres réels. Pour combler cet écart final, les chercheurs ont ajouté une seconde étape : une recherche guidée qui vérifiait les nombres proches de la meilleure supposition de l'ordinateur. Ils ont utilisé une méthode de filtrage pour ignorer les nombres qui ne pouvaient pas être premiers, réduisant ainsi considérablement le travail requis. Pour un nombre de 100 bits, l'ensemble du processus, de la configuration initiale à la découverte des facteurs finaux, a pris un peu plus de six minutes sur une seule machine. C'est nettement plus rapide que les méthodes traditionnelles, qui prendraient des heures pour la même tâche.

Les chercheurs ont testé leur pipeline sur des nombres allant de 16 à 128 bits. Bien qu'ils aient réussi à factoriser des nombres de 100 bits en quelques minutes, ils ont noté que la méthode repose toujours sur une étape de recherche finale pour trouver la réponse exacte. La vitesse de cette étape finale dépend fortement de la proximité de la supposition initiale avec la vérité. L'équipe a constaté que leur méthode fournissait systématiquement un meilleur point de départ que les suppositions plus anciennes et plus simples, ce qui réduisait considérablement le temps nécessaire pour la recherche finale. Ils ont également démontré que l'utilisation d'une technique mathématique spécifique connue sous le nom de méthode de Coppersmith pourrait accélérer davantage le processus pour les nombres plus grands, réduisant potentiellement le temps de mois en jours pour les nombres de 128 bits.

Ce travail ne brise pas les normes de chiffrement actuelles, car les nombres testés sont bien plus petits que ceux utilisés dans la sécurité réelle, qui impliquent généralement des nombres de centaines de chiffres. Cependant, il prouve qu'un ordinateur classique, lorsqu'il est guidé par la bonne structure mathématique et optimisé pour le traitement parallèle, peut résoudre ce type de problème beaucoup plus efficacement qu'on ne le pensait auparavant. L'étude suggère que le goulot d'étranglement n'est plus la vitesse brute de l'ordinateur, mais plutôt la capacité à affiner la supposition initiale. Si les améliorations futures peuvent rendre l'ordinateur encore plus proche de la solution, l'étape de recherche finale pourrait devenir si petite que l'ensemble du processus pourrait un jour s'exécuter en temps polynomial, une vitesse théorique qui changerait le paysage de la cryptographie. Pour l'instant, les chercheurs ont montré qu'en respectant la forme unique du problème et en utilisant la puissance massive du traitement parallèle des puces graphiques modernes, il est possible de transformer un verrou mathématique apparemment impossible en un puzzle soluble.