UN NOMBRE DE 155 CHIFFRES DÉCOUPÉ SUR CARTES GRAPHIQUES

Décomposer un grand nombre en facteurs premiers est difficile, et cette difficulté compte en cryptographie — c’est pourquoi l’article prend soin de dire ce que son résultat ne menace pas. Des nombres publics, les « défis RSA », servent de bancs d’essai aux méthodes de factorisation. RSA-155 en fait partie : 155 chiffres, soit 512 bits.

Deux cribles, deux palmarès

Deux familles d’algorithmes dominent. Le crible algébrique est le champion des très grands nombres : il a découpé RSA-155 dès 1999 et, selon l’article, le record général est aujourd’hui un nombre de 270 chiffres, RSA-896, en 2026. Le crible quadratique, plus ancien, est asymptotiquement plus lent et, selon les auteurs eux-mêmes, « le mauvais outil » pour les records généraux. Il a pourtant son propre palmarès : le plus grand nombre découpé avec lui était RSA-150, en juin 2025, pour 11 664 heures-cœur de processeur.

Le crible quadratique traque une multitude de petits nombres qui se factorisent entièrement sur un ensemble de petits premiers, puis les combine par algèbre linéaire pour obtenir deux carrés x² et y² égaux modulo N. Un plus grand commun diviseur révèle alors un facteur. Sur ordinateur, c’est un cauchemar pour les processeurs graphiques (GPU) : les accès mémoire s’éparpillent bien au-delà de tout cache, les tests regorgent de branchements, et l’algèbre finale se fait dans une arithmétique binaire qu’aucune bibliothèque de constructeur ne prend en charge. Les travaux antérieurs n’accéléraient que certaines étapes.

Tout sur la carte graphique

Fabian Januszewski et Christoph Heinrichs, de l’institut de mathématiques de l’université de Paderborn, en Allemagne, ont construit CUDA-MPQS, un crible quadratique en code libre dont chaque étape — préparation des polynômes, criblage, vérification des candidats, appariement des résultats partiels, construction de la matrice, résolution et racine carrée finale — tourne sur le GPU. Le processeur classique ne fait qu’orchestrer, configurer et gérer les entrées-sorties ; les auteurs listent explicitement les quelques étapes restées de son côté. Sur un test à 100 chiffres, le GPU a été occupé 99,9 % du temps de criblage, sans jamais attendre le processeur.

Le passage à grande échelle a révélé un bug subtil. À la taille de RSA-155, un compteur 8 bits utilisé pendant le criblage débordait précisément sur les candidats les plus précieux, en éliminant silencieusement 98 à 99,5 %. L’équipe l’a remplacé par un compteur saturant dont elle prouve qu’il donne des résultats identiques.

RSA-155 en une journée environ

Le 14 juillet 2026, le programme a découpé RSA-155 en deux nombres premiers de 78 chiffres chacun, vérifiés sur le GPU et sur le processeur :

• Criblage : 64 GPU NVIDIA H100 répartis sur 16 nœuds, 10,8 heures, environ 17,3 millions de relations collectées.
• Algèbre linéaire : un seul H100 pendant 10,9 heures, sur une matrice de 16,7 millions de lignes et 684 millions d’éléments non nuls.
• Total : 700,6 GPU-heures et 242 kilowattheures, environ 24 heures du lancement aux facteurs. Le criblage représente 98,4 % du coût.

À la connaissance des auteurs, c’est le plus grand entier jamais factorisé par crible quadratique, cinq chiffres au-delà du record précédent — et avec la variante la plus simple de la méthode, qui ne garde qu’un seul « grand premier » par relation là où les records récents en utilisaient trois.

Plus rapide que les meilleurs processeurs

Sur un nombre de 100 chiffres, un seul H100 termine en 29,2 secondes, et une carte grand public RTX 5070 Ti en 51 secondes. Dans une comparaison contrôlée sur le même nombre, avec l’énergie mesurée des deux côtés, un H100 a été 3,6 à 4,2 fois plus rapide que le meilleur crible quadratique sur processeur, tournant sur 96 cœurs d’un AMD EPYC, et environ neuf à dix fois plus rapide qu’un autre logiciel de référence. Ils ont aussi refactorisé RSA-150 en 302,9 GPU-heures, contre 11 664 heures-cœur pour le record précédent — un rapport dont les auteurs soulignent qu’il ne mesure pas une accélération à armes égales.

Aucune menace pour le chiffrement

Les auteurs sont explicites : RSA-155 était déjà factorisé, ce n’est pas un record général de factorisation, et « rien ici ne réduit une marge de sécurité ». Le code est d’ailleurs plafonné par construction à environ 155 chiffres. Leur intérêt est ailleurs : montrer qu’un algorithme irrégulier et plein de branchements peut vivre entièrement sur un GPU. Ils désignent comme prochaine cible naturelle le crible par réseau au cœur du crible algébrique — un travail que d’autres ont depuis entamé, notent-ils, en factorisant RSA-260 et RSA-896 avec des portages GPU d’un logiciel existant, le second réalisé avec Claude.

Conflit d’intérêts. Les auteurs déclarent avoir utilisé des IA génératives et des outils de codage agentiques : les modèles Claude d’Anthropic (via Claude Code), ainsi que des modèles GPT d’OpenAI et Gemini de Google, pour le développement logiciel, et des modèles Claude pour la préparation des données et du manuscrit. Ils précisent que toute production de l’IA a été relue et vérifiée à la main. Claude a également rédigé le présent article.