- 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[cita requerida], 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.
Contenido
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,
- ϕ(n) = (p − 1)(q − 1) = n + 1 − s,
- σ(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[1] 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 RSA-576 174 576 $10,000 USD 3 de diciembre de 2003 Jens Franke et al., Universidad de Bonn RSA-180 180 596 abierto RSA-190 190 629 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 abierto RSA-704 212 704 $30,000 USD abierto RSA-220 220 729 abierto RSA-230 230 762 abierto RSA-232 232 768 abierto RSA-768 232 768 $50,000 USD abierto RSA-240 240 795 abierto RSA-250 250 829 abierto RSA-260 260 862 abierto RSA-270 270 895 abierto RSA-896 270 896 $75,000 USD abierto RSA-280 280 928 abierto RSA-290 290 962 abierto RSA-300 300 995 abierto RSA-309 309 1024 abierto RSA-1024 309 1024 $100,000 USD abierto RSA-310 310 1028 abierto RSA-320 320 1061 abierto RSA-330 330 1094 abierto RSA-340 340 1128 abierto RSA-350 350 1161 abierto RSA-360 360 1194 abierto RSA-370 370 1227 abierto RSA-380 380 1261 abierto RSA-390 390 1294 abierto RSA-400 400 1327 abierto RSA-410 410 1360 abierto RSA-420 420 1393 abierto RSA-430 430 1427 abierto RSA-440 440 1460 abierto RSA-450 450 1493 abierto RSA-460 460 1526 abierto RSA-1536 463 1536 $150,000 USD abierto RSA-470 470 1559 abierto RSA-480 480 1593 abierto RSA-490 490 1626 abierto RSA-500 500 1659 abierto RSA-617 617 2048 abierto RSA-2048 617 2048 $200,000 USD abierto - ↑ La seguridad de RSA retiró el RSA-150 del desafío original, pero fue factorizado de todas formas.
Véase también
- Problema RSA
- The Magic Words are Squeamish Ossifrage, la solución encontrada en 1994 a RSA-129, el primer desafío, propuesto en 1977
Enlaces externos
Categorías:- Competiciones de matemática
- Computabilidad
- Premios de matemática
- Premios de ciencias de la computación
- Concursos
Wikimedia foundation. 2010.
