Cognition a annoncé le 9 septembre que son chercheur Eric Lu avait utilisé Devin, l'agent de programmation développé en interne par l'entreprise, pour mener à bien la factorisation de RSA-260, actuellement le plus grand record public du défi de factorisation RSA. Le précédent record, RSA-250, datait de février 2020, soit six ans et demi plus tôt.
RSA-260 est un nombre décimal de 260 chiffres, décomposé en deux nombres premiers de 130 chiffres. L'algorithme utilisé n'a rien de nouveau : il s'agit toujours du crible général du corps de nombres (GNFS), la méthode standard pour factoriser de grands entiers depuis les années 1990. Le changement se situe au niveau de l'implémentation : l'ensemble du pipeline est passé des clusters CPU aux GPU.
À quoi ont servi les 4900 GPU-jours
La répartition donnée par Cognition est la suivante : sélection polynomiale, 643 GPU-jours ; crible en réseau, 3813 GPU-jours ; résolution du système linéaire, 467 GPU-jours. L'étape de crible absorbe plus des trois quarts de la puissance de calcul, ce qui correspond au profil habituel du GNFS.
L'élément clé est un cribleur en réseau sur GPU nommé glas, réécrit en CUDA, combiné à une version modifiée de CADO-NFS et à une variante de l'algorithme de Wiedemann par blocs optimisée pour GPU. Selon Cognition, cette implémentation a réduit le coût unitaire du crible d'environ un ordre de grandeur.
CADO-NFS est justement le logiciel open source utilisé par l'équipe française qui a factorisé RSA-250 en 2020. Même base de code, backend matériel différent : l'écart de six ans se retrouve dans ces deux chiffres.
Ce que fait Devin ici relève de l'ingénierie, pas de la découverte mathématique : optimisation du code, réglage des paramètres, gestion du cluster. Cognition le décrit dans son billet comme un « ingénieur logiciel suffisamment compétent pour résoudre des problèmes à la croisée de la théorie algorithmique des nombres et de l'ingénierie de performance GPU ».
La contribution humaine figure elle aussi dans les données publiées : 233 sessions, 82 702 mots d'instructions. En moyenne plus de 300 mots par session, soit à peu près le volume d'annotations d'une revue de code. Ce n'est pas une exécution sans supervision, mais une personne accompagnée d'un outil capable de travailler en continu, qui a comprimé en trois semaines un travail nécessitant auparavant une équipe coordonnée pendant des mois.
Ce que donne l'extrapolation
Cognition fournit au passage deux estimations extrapolées, toutes deux présentées comme des calculs approximatifs aux prix actuels des GPU : la difficulté de RSA-1024 serait environ 78 fois celle de RSA-260, pour un coût d'environ 30 millions de dollars ; celle de RSA-2048 serait 9,12 billions de fois supérieure, pour un coût chiffré à 3,77×10^16 dollars.
Le premier chiffre mérite qu'on s'y attarde. Un ordre de grandeur de 30 millions de dollars, des institutions étatiques peuvent se le permettre, tout comme de grandes entreprises. RSA-1024 n'est plus recommandé dans les standards depuis longtemps, mais il subsiste encore dans des appareils embarqués, des signatures de firmware anciennes et quelques chaînes de certificats qui ne sont plus maintenues. L'écart d'environ un milliard de fois entre les deux chiffres est toute la raison pour laquelle le 2048 bits tient encore.
En élargissant la chronologie des records : en 1999, RSA-155 avait été factorisé avec une estimation publique d'environ 8000 MIPS-ans ; fin 2009, RSA-768 converti sur un seul cœur Opteron à 2,2 GHz équivalait à environ 2000 ans ; en 2020, RSA-250 représentait 2700 cœurs-ans ; cette fois, ce sont 13,5 GPU-ans. Les trois premiers progrès venaient surtout de la loi de Moore et de l'optimisation des algorithmes, à un rythme d'environ une décennie par palier. Dans ce bond-ci, le changement de génération matérielle et la question de « qui écrit ce code CUDA » se superposent.
Ce qui reste sans réponse
L'annonce de Cognition ne précise pas si l'article et le code seront intégralement publiés, ni si glas sera open source. Aucun tiers indépendant n'a encore reproduit ce calcul — RSA-250 avait, à l'époque, été validé de manière croisée par plusieurs équipes sur la base des paramètres de crible, alors que ce résultat-ci ne repose pour l'instant que sur les données d'une seule partie.
Le résultat de la factorisation en lui-même est facile à vérifier, il suffit de multiplier les deux nombres premiers. Ce qui est difficile à vérifier, c'est le compte des coûts : quel modèle de GPU, à quel prix unitaire, et si les tentatives infructueuses ont été comptées dans les 4900 GPU-jours — l'annonce ne détaille pas poste par poste. Ce que signifie le chiffre de 400 000 dollars pour une évaluation de sécurité dépend précisément de ces détails.
Sources : blog technique officiel de Cognition, annonce de factorisation de RSA-250 sur caramba.loria.fr, CocoLoop ; les chiffres en GPU-jours et cœurs-ans sont cités tels quels d'après chaque annonce d'origine, sans conversion unifiée.