Contexte et objectif
Le défi RSA‑260, un nombre de 260 décimales, constitue le record actuel du RSA Factoring Challenge. La factorisation a été annoncée par l’équipe de recherche Cognition, qui a exploité un GNFS (General Number Field Sieve) optimisé pour GPU. Le précédent record, RSA‑250, avait été atteint en février 2020, montrant que chaque avancée de quelques dizaines de décimales nécessite des gains d’efficacité substantiels.
Le projet s’inscrivait dans l’optimisation d’un ordonnanceur de tâches destiné à exploiter du calcul « disaggregated ». En mobilisant des nœuds GPU inoccupés sur des racks NVL72 (18 machines reliées par NVLink), les auteurs ont pu transformer une fraction de capacité de calcul en une puissance de factorisation sans coût marginal.
Architecture du GNFS GPU
La mise en œuvre repose sur une version fortement modifiée de CADO‑NFS. Aucun progrès algorithmique n’a été introduit ; l’innovation réside dans le portage du lattice sieving et de la résolution de systèmes linéaires creux sur GPU. Le lattice sieving représente plus de 75 % du temps total (3 813 GPU‑days) et bénéficie d’une parallélisation « embarrassingly parallel » sur des milliards d’unités de travail, chaque unité pouvant être exécutée sur un nœud isolé et préemptée instantanément.
Le processus complet s’est déroulé en trois étapes : sélection de polynômes (643 GPU‑days, anormalement élevée à cause d’erreurs d’opérateur), sieving (3 813 GPU‑days) et résolution linéaire (467 GPU‑days, dont 7 % d’échecs dus à des crashs ou à la préemption). Au total, la factorisation a consommé 4 900 GPU‑days, soit l’équivalent de 13,5 années GPU, pour un coût estimé à 400 000 $ aux tarifs du marché.
Analyse des coûts et performances
Le facteur de coût a été réduit d’un facteur d’environ 10 par rapport à l’état de l’art public précédent, grâce à l’utilisation du lattice sieving GPU et à l’exploitation de capacité excédentaire. En extrapolant le modèle de complexité du GNFS, le facteur RSA‑1024 (309 décimales) nécessiterait environ 78 fois plus de calcul que RSA‑260, ce qui conduit à une estimation de 30 M$ en dépenses GPU pour une factorisation complète.
En revanche, RSA‑2048 (617 décimales) reste « environ un milliard de fois plus difficile » que RSA‑260 selon les projections GNFS, et les gains observés n’affectent pas de manière significative la viabilité de son cassage avec les ressources actuelles.
Implications pour la cryptanalyse et le calcul scientifique
Le principal enseignement est la réduction du barrier to entry : des équipes disposant d’un accès à des GPU modernes peuvent, sans matériel spécialisé, atteindre des records de factorisation autrefois réservés à des laboratoires nationaux. Cette démocratisation ouvre la porte à d’autres domaines de calcul intensif où les tâches sont hautement parallélisables, comme la simulation de modèles physiques ou l’entraînement de grands modèles de langage.
Enfin, le succès repose sur un ingénieur logiciel autonome (« Devin ») qui a géré l’ensemble du pipeline, de la mesure de performance à l’optimisation du scheduler. Cette approche montre que, dans certains cas, un seul développeur hautement spécialisé peut remplacer une équipe pluridisciplinaire, accélérant ainsi le cycle de recherche et réduisant les coûts opérationnels.
