La factorización de números enteros es el proceso de determinar qué números primos dividen a un número entero positivo dado . Hacer esto rápidamente tiene aplicaciones en criptografía . La dificultad depende tanto del tamaño como de la forma del número y de sus factores primos ; actualmente es muy difícil factorizar semiprimos grandes (y, de hecho, la mayoría de los números que no tienen factores pequeños).
La primera factorización distribuida de gran magnitud fue la RSA-129 , un número de desafío de 129 dígitos descrito en el artículo de Scientific American de 1977 que popularizó por primera vez el criptosistema RSA. Se factorizó entre septiembre de 1993 y abril de 1994, utilizando MPQS , con relaciones aportadas por unas 600 personas a través de Internet, y las etapas finales del cálculo se realizaron en un superordenador MasPar en Bell Labs.
Entre enero y agosto de 1999, RSA-155 , un número de desafío de 155 dígitos preparado por la compañía RSA, se factorizó utilizando GNFS con relaciones aportadas nuevamente por un grupo grande, y las etapas finales del cálculo se realizaron en poco más de nueve días en la supercomputadora Cray C916 en el Centro de Computación Académica SARA de Ámsterdam.
En enero de 2002, Franke et al. anunciaron la factorización de un cofactor de 158 dígitos de 2 953 + 1, utilizando un par de meses en alrededor de 25 PC de la Universidad de Bonn , y las etapas finales se realizaron utilizando un grupo de seis PC Pentium-III.
En abril de 2003, el mismo equipo factorizó el RSA-160 de 160 dígitos utilizando alrededor de cien CPU en BSI , y las etapas finales del cálculo se realizaron utilizando 25 procesadores de una supercomputadora SGI Origin .
El RSA-576 de 576 bits (174 dígitos) fue factorizado por Franke, Kleinjung y miembros de la colaboración NFSNET en diciembre de 2003, utilizando recursos de BSI y la Universidad de Bonn; poco después, Aoki, Kida, Shimoyama, Sonoda y Ueda anunciaron que habían factorizado un cofactor de 164 dígitos de 2 1826 + 1.
Aoki, Kida, Shimoyama y Ueda factorizaron un cofactor de 176 dígitos de 11 281 + 1 entre febrero y mayo de 2005 utilizando máquinas en NTT y la Universidad Rikkyo en Japón. [1]
El número de desafío RSA-200 de 663 bits (200 dígitos) fue factorizado por Franke, Kleinjung et al. entre diciembre de 2003 y mayo de 2005, utilizando un grupo de 80 procesadores Opteron en BSI en Alemania; el anuncio se realizó el 9 de mayo de 2005. [2] Más tarde (noviembre de 2005) factorizaron el número de desafío RSA-640 ligeramente más pequeño .
El 12 de diciembre de 2009, un equipo que incluía investigadores del CWI , la EPFL , INRIA y NTT además de los autores del registro anterior factorizaron RSA-768 , un semiprimo de 232 dígitos. [3] Utilizaron el equivalente a casi 2000 años de computación en un solo núcleo AMD Opteron de 2,2 GHz .
En noviembre de 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé y Paul Zimmermann factorizaron el RSA-240 de 795 bits (240 dígitos) . [4] [5]
En febrero de 2020, se completó la factorización del RSA-250 de 829 bits (250 dígitos). [6]
12 151 − 1, de 542 bits (163 dígitos), fue factorizado entre abril y julio de 1993 por un equipo del CWI y la Universidad Estatal de Oregón . [7]
2 773 + 1, de 774 bits (233 dígitos), fue factorizado entre abril y noviembre de 2000 por 'The Cabal', con el paso de matriz realizado durante 250 horas en el Cray también utilizado para RSA-155. [8]
La factorización de la ecuación 2 809 − 1, de 809 bits (244 dígitos), se anunció a principios de enero de 2003. El tamizado se realizó en el CWI, en el Instituto de Computación Científica y el Departamento de Matemáticas Pura de la Universidad de Bonn, y utilizando recursos privados de J. Franke, T. Kleinjung y la familia de F. Bahr. El paso de álgebra lineal lo realizó P. Montgomery en SARA en Ámsterdam. [9]
6 353 − 1, de 911 bits (275 dígitos), fue factorizado por Aoki, Kida, Shimoyama y Ueda entre septiembre de 2005 y enero de 2006 utilizando SNFS . [10]
2 1039 − 1, de 1039 bits (313 dígitos) (aunque ya se conocía un factor de 23 bits) fue factorizado entre septiembre de 2006 y mayo de 2007 por un grupo que incluía a K. Aoki, J. Franke, T. Kleinjung, AK Lenstra y DA Osvik, utilizando computadoras en NTT , EPFL y la Universidad de Bonn . [11] [12]
2 1061 − 1, de 1061 bits (320 dígitos) fue factorizado entre principios de 2011 y el 4 de agosto de 2012 por un grupo dirigido por Greg Childers en CSU Fullerton, utilizando el proyecto BOINC nfs@home para aproximadamente 300 años-CPU de tamizado; el álgebra lineal se ejecutó en el clúster Trestles en SDSC y el clúster Lonestar en TACC y necesitó 35 años-CPU adicionales. [13]
Todas las partes no factorizadas de los números 2 n − 1 con n entre 1000 y 1200 fueron factorizadas mediante un enfoque de tamiz de números múltiples en el que gran parte del paso de tamizado se podía realizar simultáneamente para múltiples números, por un grupo que incluía a T. Kleinjung, J. Bos y AK Lenstra , a partir de 2010. [14] Para ser precisos, n = 1081 (326 dígitos) se completó el 11 de marzo de 2013; n = 1111 (335 dígitos) el 13 de junio de 2013; n = 1129 (340 dígitos) el 20 de septiembre de 2013; n = 1153 (348 dígitos) el 28 de octubre de 2013; n = 1159 (349 dígitos) el 9 de febrero de 2014; n = 1177 (355 dígitos) el 29 de mayo de 2014, n = 1193 (360 dígitos) el 22 de agosto de 2014 y n = 1199 (361 dígitos) el 11 de diciembre de 2014; el primer anuncio detallado se realizó a fines de agosto de 2014. El esfuerzo total para el proyecto es del orden de 7500 años de CPU en Opterons de 2,2 GHz, con aproximadamente 5700 años dedicados al tamizado y 1800 años al álgebra lineal.
A finales de 2007, gracias a la constante disminución de los precios de la memoria, la fácil disponibilidad de ordenadores multinúcleo de 64 bits y la disponibilidad del eficiente código de tamizado (desarrollado por Thorsten Kleinjung del grupo de Bonn) a través de ggnfs [15] y de un robusto software de código abierto como msieve [16] para las etapas de acabado, números de forma especial de hasta 750 bits (226 dígitos) y números de forma general de hasta aproximadamente 520 bits (157 dígitos) pueden factorizarse en unos pocos meses en unos pocos PC por una sola persona sin ninguna experiencia matemática especial. [17] Estos límites aumentan a aproximadamente 950 bits (286 dígitos) [18] y 600 bits (181 dígitos) [19] si fuera posible asegurar la colaboración de unas pocas docenas de PC para el tamizado; actualmente, la cantidad de memoria y la potencia de CPU de una sola máquina para la etapa de acabado son barreras iguales para el progreso.
En 2009, Benjamin Moody factorizó una clave RSA de 512 bits (155 dígitos) utilizada para firmar la calculadora gráfica TI-83 utilizando un software encontrado en Internet; esto eventualmente condujo a la controversia de la clave de firma de Texas Instruments .
En septiembre de 2013, Ryan Propper [20] factorizó el RSA-210 de 696 bits (210 dígitos) utilizando recursos institucionales; entre marzo de 2013 y octubre de 2014, un usuario conocido como WraithX [21] completó otro número de 210 dígitos (el término 117 en la secuencia de primos que comienza con 49), utilizando $7600 en tiempo de procesamiento en máquinas Amazon EC2 [22] para el tamizado, y cuatro meses en un Xeon E5-2687W v1 dual para el álgebra lineal.
El número más grande factorizado de manera confiable [ aclaración necesaria ] por el algoritmo de Shor es 21, que fue factorizado en 2012. [23] 15 había sido factorizado previamente por varios laboratorios.
En abril de 2012, un grupo dirigido por Xinhua Peng informó sobre la factorización de 143 = 13 × 11 mediante una computadora cuántica adiabática de RMN a temperatura ambiente (300 K). [24] En noviembre de 2014 se descubrió que, de hecho, el experimento de 2012 también había factorizado números mucho mayores sin saberlo. [ aclaración necesaria ] [25] [26] En abril de 2016, el número de 18 bits 200.099 se factorizó utilizando recocido cuántico en un procesador cuántico D-Wave 2X . [27] Poco después, se factorizó 291 311 utilizando RMN a una temperatura superior a la ambiente. [28] A finales de 2019, Zapata computing afirmó haber factorizado 1.099.551.473.989, [29] y en 2021 publicó un artículo que describe este cálculo. [30] En 2024, se propuso un nuevo enfoque para integrar problemas de factorización prima en recocedores cuánticos, lo que llevó a (i) la integración de problemas de factorización prima de 21×12 en una arquitectura D-Wave Pegasus; (ii) la factorización de 8.219.999 mediante el uso de un recocedor cuántico sin explotar técnicas híbridas. [31]
Como tal, las afirmaciones de factorización con computadoras cuánticas han sido criticadas por depender en gran medida del cálculo clásico para reducir la cantidad de qubits necesarios. [32] [33] Por ejemplo, la factorización de 1.099.551.473.989 se basó en el preprocesamiento clásico para reducir el problema a un circuito cuántico de tres qubits. [30] Además, los tres números factorizados en este artículo (200.099, 291.311 y 1.099.551.473.989) se pueden factorizar fácilmente utilizando el método de factorización de Fermat , que requiere solo 3, 1 y 1 iteraciones del bucle respectivamente.
{{cite web}}: CS1 maint: copia archivada como título ( enlace ){{cite web}}: CS1 maint: copia archivada como título ( enlace )