# Competición de factorización RSA

La Competición de factorización RSA fue un desafío propuesto por los Laboratorios RSA el 18 de marzo de 1991 para fomentar la investigación en la teoría computacional de números y la dificultad práctica de la factorización de números enteros grandes. Publicaron una lista de semiprimos (números que tienen exactamente dos factores primos) conocida como los números RSA, con un premio en metálico para la factorización con éxito de algunos de ellos. El más pequeño de todos, un número con 100 cifras decimales conocido como RSA-100 fue factorizado en pocos días, pero la mayoría de los números más grandes aún no han sido factorizados y se espera que permanezcan así durante bastante tiempo. La compañía RSA canceló la competición en el año 2007.
Este desafío estaba diseñado para seguir el ritmo al estado del arte en la factorización de enteros. Una aplicación importante es la elección de la longitud de la clave del algoritmo de cifrado mediante clave pública de RSA. Los avances en este desafío deberían ser un indicador de qué longitudes de clave son todavía seguras y por cuánto tiempo. Como los laboratorios RSA son los proveedores de los productos basados en RSA, el desafío se usa como incentivo a la comunidad académica para atacar el núcleo de sus soluciones, esto es, para comprobar su fortaleza.
Los primeros números RSA generados desde RSA-100 hasta RSA-500 fueron etiquetados de acuerdo con su número de cifras decimales; sin embargo, a partir de RSA-576 se cuentan las cifras en el sistema binario. La excepción a esto es el RSA-617, que fue creado antes del cambio del sistema de numeración.

## Matemáticas

Sea $n$ un número RSA producto de dos primos $p$ y $q$, de forma que
    $n=pq$.
El problema es encontrar esos dos primos, conociendo solo $n$.
Sea $s=p+q$; entonces los valores de algunas funciones aritméticas básicas son
    $d(n)=2$,
    $\phi (n)=(p-1)(q-1)=n+1-s$,
    $\sigma (n)=(p+1)(q+1)=n+1+s$.

## Los premios y los récords

La tabla siguiente hace un recorrido por todos los números RSA.
    Los números del desafío en líneas rosas son números expresados en base 10, mientras que los de las líneas amarillas son números expresados en base 2, y que tenían un premio asignado.
| Número RSA | Cifras decimales | Cifras binarias | Premio ofrecido | Factorizado en | Factorizado por |
| RSA-100 | 100 | 330 | | abril de 1991 | Arjen K. Lenstra |
| RSA-110 | 110 | 364 | | abril de 1992 | Arjen K. Lenstra y M.S. Manasse |
| RSA-120 | 120 | 397 | | junio de 1993 | T. Denny et al. |
| RSA-129 | 129 | 426 | $100 USD | abril de 1994 | Arjen K. Lenstra et al. |
| RSA-130 | 130 | 430 | | 10 de abril de 1996 | Arjen K. Lenstra et al. |
| RSA-140 | 140 | 463 | | 2 de febrero de 1999 | Herman J. J. te Riele et al. |
| RSA-150 | 150 | 496 | | 16 de abril de 2004 | Kazumaro Aoki et al. |
| RSA-155 | 155 | 512 | | 22 de agosto de 1999 | Herman J. J. te Riele et al. |
| RSA-160 | 160 | 530 | | 1 de abril de 2003 | Jens Franke et al., Universidad de Bonn |
| RSA-170 | 170 | 563 | | abierto | abierto |
| RSA-576 | 174 | 576 | $10,000 USD | 3 de diciembre de 2003 | Jens Franke et al., Universidad de Bonn |
| RSA-180 | 180 | 596 | | abierto | abierto |
| RSA-190 | 190 | 629 | | abierto | abierto |
| RSA-640 | 193 | 640 | $20,000 USD | 2 de noviembre de 2005 | Jens Franke et al., Universidad de Bonn |
| RSA-200 | 200 | 663 | | 9 de mayo de 2005 | Jens Franke et al., Universidad de Bonn |
| RSA-210 | 210 | 696 | | 26 de septiembre de 2013 | Ryan Propper |
| RSA-704 | 212 | 704 | $30,000 USD | abierto | abierto |
| RSA-220 | 220 | 729 | | abierto | abierto |
| RSA-230 | 230 | 762 | | abierto | abierto |
| RSA-232 | 232 | 768 | | abierto | abierto |
| RSA-768 | 232 | 768 | $50,000 USD | 12 de diciembre de 2009 | A six-institution research team led by T. Kleinjung |
| RSA-240 | 240 | 795 | | 2 de diciembre de 2019 | Fabrice Boudot et al. |
| RSA-250 | 250 | 829 | | abierto | abierto |
| RSA-260 | 260 | 862 | | abierto | abierto |
| RSA-270 | 270 | 895 | | abierto | abierto |
| RSA-896 | 270 | 896 | $75,000 USD | abierto | abierto |
| RSA-280 | 280 | 928 | | abierto | abierto |
| RSA-290 | 290 | 962 | | abierto | abierto |
| RSA-300 | 300 | 995 | | abierto | abierto |
| RSA-309 | 309 | 1024 | | abierto | abierto |
| RSA-1024 | 309 | 1024 | $100,000 USD | abierto | abierto |
| RSA-310 | 310 | 1028 | | abierto | abierto |
| RSA-320 | 320 | 1061 | | abierto | abierto |
| RSA-330 | 330 | 1094 | | abierto | abierto |
| RSA-340 | 340 | 1128 | | abierto | abierto |
| RSA-350 | 350 | 1161 | | abierto | abierto |
| RSA-360 | 360 | 1194 | | abierto | abierto |
| RSA-370 | 370 | 1227 | | abierto | abierto |
| RSA-380 | 380 | 1261 | | abierto | abierto |
| RSA-390 | 390 | 1294 | | abierto | abierto |
| RSA-400 | 400 | 1327 | | abierto | abierto |
| RSA-410 | 410 | 1360 | | abierto | abierto |
| RSA-420 | 420 | 1393 | | abierto | abierto |
| RSA-430 | 430 | 1427 | | abierto | abierto |
| RSA-440 | 440 | 1460 | | abierto | abierto |
| RSA-450 | 450 | 1493 | | abierto | abierto |
| RSA-460 | 460 | 1526 | | abierto | abierto |
| RSA-1536 | 463 | 1536 | $150,000 USD | abierto | abierto |
| RSA-470 | 470 | 1559 | | abierto | abierto |
| RSA-480 | 480 | 1593 | | abierto | abierto |
| RSA-490 | 490 | 1626 | | abierto | abierto |
| RSA-500 | 500 | 1659 | | abierto | abierto |
| RSA-617 | 617 | 2048 | | abierto | abierto |
| RSA-2048 | 617 | 2048 | $200,000 USD | abierto | abierto |
* ↑ La seguridad de RSA retiró el RSA-150 del desafío original, pero fue factorizado de todas formas.