Nombre RSA
# Nombre RSA

En mathématiques, les nombres RSA sont des nombres semi-premiers (c'est-à-dire des nombres qui ont exactement deux facteurs premiers), tels que ceux utilisés par le chiffrement RSA. Le but de la compétition de factorisation RSA, lancée en mars 1991 et organisée par la société RSA Security, était d'obtenir leur factorisation. Des récompenses étaient offertes pour les factorisations de RSA-576 à RSA-2048 jusqu'en mai 2007, date à laquelle la société RSA a arrêté la compétition. Cependant des équipes ont continué et continuent depuis à travailler sur la factorisation des nombres restant.

Les premiers nombres RSA générés, de RSA-100 à RSA-500, furent baptisés en référence à leurs nombres de chiffres décimaux ; plus tard, néanmoins, en commençant avec RSA-576, les chiffres binaires furent comptés à la place. Une exception à ceci est le nombre RSA-617, qui a été créé avant le changement du schéma de numération.

## Problème

Soit n un nombre RSA. Il existe des nombres premiers p et q tels que

    $n=pq.$

Le problème est de trouver ces deux nombres premiers, connaissant seulement n.

## Les prix et les records

La table suivante donne une vue d'ensemble de tous les nombres RSA (les prix mentionnés étaient proposés pour une factorisation avant mai 2007):

| Nombre RSA | Chiffres décimaux | Chiffres binaires | Prix offert | Factorisé le | Factorisé par |
| - | - | - | - | - | - |
| RSA-100 | 100 | 330 | | 1er avril 1991 | Arjen K. Lenstra |
| RSA-110 | 110 | 364 | | 14 avril 1992 | Arjen K. Lenstra et M. S. Manasse |
| RSA-120 | 120 | 397 | | 9 juillet 1993 | T. Denny et al. |
| RSA-129 | 129 | 426 | 100 $ | 26 avril 1994 | Arjen K. Lenstra et al. |
| RSA-130 | 130 | 430 | | 10 avril 1996 | Arjen K. Lenstra et al. |
| RSA-140 | 140 | 463 | | 2 février 1999 | Herman te Riele et al. |
| RSA-150 | 150 | 496 | | 16 avril 2004 | Kazumaro Aoki et al. |
| RSA-155 | 155 | 512 | | 22 août 1999 | Herman te Riele et al. |
| RSA-160 | 160 | 530 | | 1er avril 2003 | Jens Franke et al., Université de Bonn |
| RSA-170 | 170 | 563 | | 29 décembre 2009 | D. Bonenberger et M. Krone |
| RSA-576 | 174 | 576 | 10 000 $ | 3 décembre, 2003 | Jens Franke et al., Université de Bonn |
| RSA-180 | 180 | 596 | | 12 mai 2010 | A. Danilov et I.A. Popovyan, Université d'État de Moscou |
| RSA-190 | 190 | 629 | | 8 novembre 2010 | I.Popovyan et A. Timofeev |
| RSA-640 | 193 | 640 | 20 000 $ | 2 novembre 2005 | Jens Franke et al., Université de Bonn |
| RSA-200 | 200 | 663 | | 9 mai 2005 | Jens Franke et al., Université de Bonn |
| RSA-210 | 210 | 696 | | 26 septembre 2013 | Ryan Propper |
| RSA-704 | 212 | 704 | (30 000 $) | 2 juillet 2012 | Shi Bai, Emmanuel Thomé et Paul Zimmermann |
| RSA-220 | 220 | 729 | | 13 mai 2016 | S. Bai, P. Gaudry, A. Kruppa, E. Thomé et P. Zimmermann |
| RSA-230 | 230 | 762 | | 29 août 2018 | Samuel S. Gross et al., Noblis |
| RSA-232 | 232 | 768 | | 17 février 2020 | N. L. Zamarashkin, D. A. Zheltkov et S. A. Matveev |
| RSA-768 | 232 | 768 | (50 000 $) | 12 décembre 2009 | Thorsten Kleinjung et al |
| RSA-240 | 240 | 795 | | 2 décembre 2019 | F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé, P. Zimmermann |
| RSA-250 | 250 | 829 | | 28 février 2020 | F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé, P. Zimmermann |
| RSA-260 | 260 | 862 | | ouvert | ouvert |
| RSA-270 | 270 | 895 | | ouvert | ouvert |
| RSA-896 | 270 | 896 | (75 000 $) | ouvert | ouvert |
| RSA-280 | 280 | 928 | | ouvert | ouvert |
| RSA-290 | 290 | 962 | | ouvert | ouvert |
| RSA-300 | 300 | 995 | | ouvert | ouvert |
| RSA-309 | 309 | 1024 | | ouvert | ouvert |
| RSA-1024 | 309 | 1024 | (100 000 $) | ouvert | ouvert |
| RSA-310 | 310 | 1028 | | ouvert | ouvert |
| RSA-320 | 320 | 1061 | | ouvert | ouvert |
| RSA-330 | 330 | 1094 | | ouvert | ouvert |
| RSA-340 | 340 | 1128 | | ouvert | ouvert |
| RSA-350 | 350 | 1161 | | ouvert | ouvert |
| RSA-360 | 360 | 1194 | | ouvert | ouvert |
| RSA-370 | 370 | 1227 | | ouvert | ouvert |
| RSA-380 | 380 | 1261 | | ouvert | ouvert |
| RSA-390 | 390 | 1294 | | ouvert | ouvert |
| RSA-400 | 400 | 1327 | | ouvert | ouvert |
| RSA-410 | 410 | 1360 | | ouvert | ouvert |
| RSA-420 | 420 | 1393 | | ouvert | ouvert |
| RSA-430 | 430 | 1427 | | ouvert | ouvert |
| RSA-440 | 440 | 1460 | | ouvert | ouvert |
| RSA-450 | 450 | 1493 | | ouvert | ouvert |
| RSA-460 | 460 | 1526 | | ouvert | ouvert |
| RSA-1536 | 463 | 1536 | (150 000 $) | ouvert | ouvert |
| RSA-470 | 470 | 1559 | | ouvert | ouvert |
| RSA-480 | 480 | 1593 | | ouvert | ouvert |
| RSA-490 | 490 | 1626 | | ouvert | ouvert |
| RSA-500 | 500 | 1659 | | ouvert | ouvert |
| RSA-2048 | 617 | 2048 | (200 000 $) | ouvert | ouvert |

## Liste des nombres RSA

### Nombres RSA déjà factorisés

**RSA-100**

RSA-100 a été factorisé en avril 1991 :

**RSA-110**

RSA-110 a été factorisé en avril 1992 :

**RSA-120**

RSA-120 a été factorisé en juin 1993 :

**RSA-129**

RSA-129 a été factorisé en avril 1994 par une équipe conduite par Arjen K. Lenstra, utilisant 600 ordinateurs connectés sur Internet et un algorithme de crible quadratique (MPQS). Un prix de 100 $ USD a été attribué par RSA Security pour sa factorisation, qui a été donné à la Free Software Foundation.

L'épreuve de factorisation incluait un message chiffré avec RSA-129. Lors de son déchiffrement en utilisant la factorisation, le message se révéla être « The Magic Words are Squeamish Ossifrage (en) » (les mots magiques sont « délicat ossifrage »).

**RSA-130**

Il a été factorisé le 10 avril 1996 par une équipe conduite par Arjen K. Lenstra et composée de Jim Cowie, Marije Elkenbracht-Huizing, Wojtek Furmanski, Peter Montgomery, Damian Weber et Joerg Zayer :

La factorisation a été trouvée en utilisant l'algorithme du crible sur les corps de nombres généralisé (GNFS) et le polynôme :

qui a pour racine modulo RSA-130 :

**RSA-140**

Il a été factorisé le 2 février 1999 par une équipe conduite par Herman te Riele et composée de Stefania Cavallar, Bruce Dodson, Arjen K. Lenstra, Paul Leyland, Walter Lioen, Peter Montgomery, Brian Murphy et Paul Zimmermann. La factorisation a été trouvée en utilisant l'algorithme Number Field Sieve (GNFS) et fut estimée à 2000 années MIPS de temps de calcul :

**RSA-150**

Il a été retiré de la compétition par RSA Security. RSA-150 a été factorisé en deux nombres premiers de 75 chiffres par Aoki et al. en 2004 :

**RSA-155**

Il a été factorisé le 22 août 1999 par une équipe conduite par Herman te Riele et composée de Stefania Cavallar, Bruce Dodson, Arjen K. Lenstra, Walter Lioen, Peter L. Montgomery, Brian Murphy, Karen Aardal, Jeff Gilchrist, Gerard Guillerm, Paul Leyland, Joel Marchand, Francois Morain, Alec Muffett, Craig Putnam, Chris Putnam et Paul Zimmermann. La factorisation a été trouvée en utilisant l'algorithme Number Field Sieve (GNFS) et fut estimée à 8000 années MIPS de temps de calcul :

**RSA-160**

Il a été factorisé le 1er avril 2003 par une équipe de l'Université de Bonn et la Bundesamt für Sicherheit in der $Informationstechnik^,$ (BSI, « Office fédéral de l'information sur la sécurité ») allemand (J. Franke, F. Bahr, T. Kleinjung, M. Lochter, M. Böhm) en utilisant l'algorithme GNFS.

**RSA-170**

RSA-170 a une longueur de 170 chiffres décimaux. Il a été factorisé 29 décembre 2009 par D. Bonenberger et M. Krone de Fachhochschule Braunschweig/Wolfenbüttel.

**RSA-576**

RSA-576 possède en tout 174 chiffres. Il a été factorisé le 3 décembre 2003 par J. Franke et T. Kleinjung de l'Université de Bonn (Allemagne) en utilisant l’algorithme $GNFS^,^,$ :

**RSA-180**

RSA-180 a une longueur de 180 chiffres décimaux et a été factorisé par S. A. Danilov et I. A. Popovyan de l'Université d'État de Moscou le 8 mai 2010 :

**RSA-190**

RSA-190 a une longueur de 190 chiffres décimaux. Il a été factorisé le 8 novembre 2010 par I.Popovyan from MSU, Russia et A. Timofeev du CWI aux Pays-Bas :

**RSA-640**

RSA-640 a une longueur de 193 chiffres décimaux, il a été factorisé le 2 novembre $2005^,$ à l'aide d'un réseau de 80 processeurs Opteron de 2,2 GHz pendant 5 mois.

L'équipe gagnante de F. Bahr, M. Boehm, J. Franke et T. Kleinjung remporta 20 000 dollars US.

**RSA-200**

RSA-200 a une longueur de 200 chiffres décimaux. Il fut factorisé le 9 mai 2005 par Friedrich Bahr, M. Böhm, Jens Franke et Thorsten Kleinjung de l'Université de Bonn (Allemagne), en utilisant le crible algébrique (GNFS) :

**RSA-210**

RSA-210 a une longueur de 210 chiffres décimaux (696 bits) et a été factorisé le 26 septembre 2013 :

**RSA-704**

RSA-704 a une longueur de 212 chiffres décimaux. Un prix d'une valeur de 30 000 $ était offert pour la réussite de sa factorisation par RSA Security, avant la clôture de la compétition. RSA-704 a depuis été factorisé par Shi Bai, Emmanuel Thomé et Paul Zimmermann. La factorisation a été annoncée le 2 juillet 2012.

**RSA-220**

RSA-220 a une longueur de 220 chiffres décimaux et n’a longtemps pas pu être factorisé. RSA-220 a toutefois été factorisé par Shi Bai, Pierrick Gaudry, Alexander Kruppa, Emmanuel Thomé et Paul Zimmerman entre décembre 2013 et mai 2016 :

**RSA-230**

RSA-230 a une longueur de 230 chiffres décimaux

La société Noblis a annoncé le 29 août 2018 que le Dr. Samuel S. Gross et son équipe avaient réussi à factoriser RSA-230.

**RSA-232**

RSA-232 a une longueur de 232 chiffres décimaux :

Il a été factorisé en février 2020 par N. L. Zamarashkin, D. A. Zheltkov et S. A. Matveev.

**RSA-768**

RSA-768 a une longueur de 232 chiffres décimaux et n'a longtemps pas pu être factorisé. Un prix d'une valeur de 50 000 $ était offert jusqu'en 2007 pour la réussite de sa factorisation par RSA Security.

La factorisation de ce nombre a toutefois été réussie le 12 décembre 2009 et (publiée le 7 janvier 2010) grâce au Crible algébrique. L'annonce a été faite sur le forum MersenneForum.

**RSA-240**

RSA-240 a une longueur de 240 chiffres décimaux (795 bits) :

Il a été factorisé en novembre 2019 par Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé et Paul Zimmermann.

**RSA-250**

RSA-250 a une longueur de 250 chiffres décimaux (829 bits) :

Il a été factorisé en février 2020 par Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé et Paul Zimmermann

### Nombres RSA pas encore factorisés

**RSA-260**

RSA-260 a une longueur de 260 chiffres décimaux et n’a pas encore été factorisé.

**RSA-270**

RSA-270 a une longueur de 270 chiffres décimaux et n’a pas encore été factorisé.

**RSA-280**

RSA-280 a une longueur de 280 chiffres décimaux et n’a pas encore été factorisé.

**RSA-290**

RSA-290 a une longueur de 290 chiffres décimaux et n’a pas encore été factorisé.

**RSA-300**

RSA-300 a une longueur de 300 chiffres décimaux et n’a pas encore été factorisé.

**RSA-309**

RSA-309 a une longueur de 309 chiffres décimaux et n’a pas encore été factorisé.

**RSA-310**

RSA-310 a une longueur de 310 chiffres décimaux et n’a pas encore été factorisé.

**RSA-320**

RSA-320 a une longueur de 320 chiffres décimaux et n’a pas encore été factorisé.

**RSA-330**

RSA-330 a une longueur de 330 chiffres décimaux et n’a pas encore été factorisé.

**RSA-340**

RSA-340 a une longueur de 340 chiffres décimaux et n’a pas encore été factorisé.

**RSA-350**

RSA-350 a une longueur de 350 chiffres décimaux et n’a pas encore été factorisé.

**RSA-360**

RSA-360 a une longueur de 360 chiffres décimaux et n’a pas encore été factorisé.

**RSA-370**

RSA-370 a une longueur de 370 chiffres décimaux et n’a pas encore été factorisé.

**RSA-380**

RSA-380 a une longueur de 380 chiffres décimaux et n’a pas encore été factorisé.

**RSA-390**

RSA-390 a une longueur de 390 chiffres décimaux et n’a pas encore été factorisé.

**RSA-400**

RSA-400 a une longueur de 400 chiffres décimaux et n’a pas encore été factorisé.

**RSA-410**

RSA-410 a une longueur de 410 chiffres décimaux et n’a pas encore été factorisé.

**RSA-420**

RSA-420 a une longueur de 420 chiffres décimaux et n’a pas encore été factorisé.

**RSA-430**

RSA-430 a une longueur de 430 chiffres décimaux et n’a pas encore été factorisé.

**RSA-440**

RSA-440 a une longueur de 440 chiffres décimaux et n’a pas encore été factorisé.

**RSA-450**

RSA-450 a une longueur de 450 chiffres décimaux et n’a pas encore été factorisé.

**RSA-460**

RSA-460 a une longueur de 460 chiffres décimaux et n’a pas encore été factorisé.

**RSA-470**

RSA-470 a une longueur de 470 chiffres décimaux et n’a pas encore été factorisé.

**RSA-480**

RSA-480 a une longueur de 480 chiffres décimaux et n’a pas encore été factorisé.

**RSA-490**

RSA-490 a une longueur de 490 chiffres décimaux et n’a pas encore été factorisé.

**RSA-500**

RSA-500 a une longueur de 500 chiffres décimaux et n’a pas encore été factorisé.

**RSA-617**

RSA-617 a une longueur de 617 chiffres décimaux et n’a pas encore été factorisé.

**RSA-896**

RSA-896 a une longueur de 270 chiffres décimaux et n'a pas encore été factorisé. Un prix d'une valeur de 75 000 $ a été offert pour la réussite de sa factorisation par RSA Security jusqu’en 2007.

**RSA-1024**

RSA-1024 a une longueur de 309 chiffres décimaux et n'a pas encore été factorisé. Jusqu'en 2007, un prix d'une valeur de 100 000 $ était offert par RSA Security pour la réussite de sa factorisation.

**RSA-1536**

RSA-1536 a une longueur de 463 chiffres décimaux et n'a pas encore été factorisé. Un prix d'une valeur de 150 000 $ a été offert pour la réussite de sa factorisation par RSA Security jusqu’en 2007.

**RSA-2048**

RSA-2048 a une longueur de 617 chiffres décimaux. Un prix d'une valeur de 200 000 $ était offert jusqu'en 2007 par RSA Security pour sa factorisation.

