Devin factorise RSA-260 sur GPU pour 400 000 $, dix fois moins cher que le record précédent

Un chercheur de Cognition a factorisé en nombres premiers le nombre RSA-260, composé de 260 chiffres décimaux, à l'aide d'agents Devin. C'est un nouveau record parmi les défis du RSA Factoring Challenge résolus publiquement : le précédent, RSA-250, avait été établi en février 2020. Les calculs ont duré environ 4 900 GPU-jours (13,5 GPU-années) et coûté environ $400 000 aux prix du marché. Selon l'estimation de l'auteur, c'est dix fois moins que le niveau public précédent.

L'auteur insiste : il n'y a pas de percée algorithmique. Il a utilisé le crible général de corps de nombres (GNFS), la méthode connue la plus efficace pour les nombres de plus d'environ 100 chiffres. La base est un CADO-NFS très largement remanié. Le gain vient, selon ses termes, de « la bonne vieille ingénierie de performance » adaptée à l'organisation de la mémoire des GPU. Il n'y a pas non plus d'ordinateur quantique, et personne n'a tenté de deviner à la main des nombres premiers de 130 chiffres.

D'où viennent les calculs

Les clusters de Cognition pour l'entraînement et l'inférence de LLM sont composés de racks NVL72, chacun comptant nominalement 18 machines reliées par un NVLink rapide. Le planificateur range les tâches dans les racks, et il reste toujours quelque part un nœud libre : réserve en cas de panne, nombre impair de machines pour une tâche qui en demande un nombre pair, 17 nœuds au lieu de 18. Au total, cela représente un pourcentage à un chiffre de la puissance globale.

Le chercheur a configuré le planificateur pour combler ces trous avec des tâches mono-nœud de priorité minimale. Il manquait encore une source de tâches interruptibles à tout moment. Le crible par réseaux (lattice sieving) convenait parfaitement : il se parallélise en milliards de petites unités de travail et supporte sans risque une préemption immédiate. Tous les records publics précédents de GNFS exécutaient cette étape uniquement sur CPU, car les branchements et les accès mémoire chaotiques pénalisaient les GPU.

Comment Devin a travaillé

Le prompt est parti le 13 août à 0:11:58, heure du Pacifique. La mission : produire un remplacement drop-in du crible CPU las de CADO-NFS, plus rapide que l'original. Deux heures plus tard, l'auteur a ajouté l'exigence de reprendre les paramètres de RSA-250, puis est allé dormir. Au matin, après sept heures d'itérations supplémentaires, Devin avait abouti.

Les agents ont ensuite optimisé le reste de la chaîne. Sur trois semaines, 3 sessions ont tourné en parallèle en moyenne, 18 au maximum. L'auteur ne revenait sur la boucle qu'une fois toutes les deux heures environ. Devin lançait lui-même les expériences, choisissait les paramètres du crible et de l'algèbre linéaire, déboguait le code et démarrait les calculs sur le cluster. L'auteur reconnaît ne pas maîtriser en profondeur les mathématiques et décrit son rôle ainsi : fixer les priorités, définir les benchmarks et repérer à temps les erreurs de direction.

Presque toutes les briques ont été réécrites : la version GPU de la première étape de sélection du polynôme, le crible GPU glas, des dup/purge et merge/replay accélérés, une nouvelle implémentation GPU de l'algorithme de Wiedemann par blocs, et GPU-sqrt. Seuls cado-nfs.py, polyselect_ropt, makefb et dup1 sont restés intacts.

Les chiffres du projet

• Au total, environ 4 900 GPU-jours, soit environ $400 000.
• Sélection du polynôme : 643 GPU-jours (anormalement élevé, à cause d'erreurs de l'opérateur).
• Crible : 3 813 GPU-jours.
• Algèbre linéaire : 467 GPU-jours, dont environ 7 % perdus en pannes et en préemptions au profit de tâches plus importantes.
• 8,3 milliards de relations linéaires obtenues sur GF(2).
• Le calcul a mobilisé quelques pour cent de la puissance du cluster, sans coût marginal.

Qu'en est-il des clés réelles ?

Selon la loi d'échelle standard du GNFS, RSA-1024 exige seulement 78 fois plus de calcul que RSA-260. L'auteur estime le coût à environ $30 millions par nombre et n'exclut pas une nouvelle division par deux après des améliorations. Les hyperscalers et les grands laboratoires d'IA en sont théoriquement capables. Mais le RSA 1024 bits est déclaré obsolète depuis 2013, et les soupçons sur les capacités des services de renseignement circulent depuis le milieu des années 2000.

RSA-2048, le standard actuel, reste environ un milliard de fois plus difficile que RSA-1024 et n'est pas affecté par ce travail. Trois choses ont changé : le prix, le nombre d'acteurs potentiels (il faut des GPU, pas du matériel spécialisé) et le fait que des non-cryptographes peuvent désormais participer à l'optimisation de la factorisation.

Que faire côté équipes

Les équipes de sécurité doivent vérifier qu'il ne reste pas de clés ni de certificats de 1024 bits dans l'infrastructure, y compris dans les appareils embarqués et les anciens services internes. Pour eux, la migration est en retard depuis longtemps. Pour les clés de 2048 bits, il n'y a pas d'urgence, mais ce résultat mérite d'entrer dans les modèles de menaces concernant les données à longue durée de vie.

Pour les équipes d'ingénierie et de recherche, l'enseignement est plus large. Des tâches mono-nœud préemptibles peuvent exploiter les restes fragmentés d'un cluster. Des agents de codage autonomes peuvent prendre en charge l'association d'une théorie pointue et d'une optimisation GPU, qui exigeait auparavant une équipe de spécialistes pendant des mois.