La factorización de enteros es el proceso de determinar qué números primos dividen a un 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 los semiprimos grandes (y, de hecho, la mayoría de los números que no tienen factores pequeños).
La primera factorización distribuida enorme fue 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 una supercomputadora 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 empresa RSA, fue factorizado 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 el Supercomputadora Cray C916 en el Centro de Computación Académica SARA Amsterdam.
En enero de 2002, Franke et al. anunció la factorización de un cofactor de 158 dígitos de 2 953 + 1, utilizando un par de meses en aproximadamente 25 PC en 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 de NTT y la Universidad de 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 hizo 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 semiprime de 232 dígitos. [3] Utilizaron el equivalente a casi 2000 años de informática en un AMD Opteron de un solo núcleo a 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', y el paso de matriz se realizó durante 250 horas en el Cray, también utilizado para RSA-155. [8]
2 809 − 1, de 809 bits (244 dígitos), se anunció su factorización a principios de enero de 2003. El tamizado se realizó en el CWI, en el Instituto de Computación Científica y en el Departamento de Matemática 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 fue realizado por 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 ordenadores de 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 encabezado por Greg Childers en CSU Fullerton, utilizando el proyecto nfs@home BOINC para aproximadamente 300 años de CPU de tamizado; el álgebra lineal se ejecutó en el grupo Trestles en SDSC y en el grupo Lonestar en TACC y necesitó 35 años de CPU adicionales. [13]
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 hizo a finales 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 en álgebra lineal.
A finales de 2007, gracias a la constante caída de los precios de la memoria, la fácil disponibilidad de ordenadores multinúcleo de 64 bits y la disponibilidad del código de tamizado eficiente (desarrollado por Thorsten Kleinjung del grupo Bonn) a través de ggnfs [15 ] y de software robusto de código abierto como msieve [16] para las etapas de acabado, se pueden factorizar 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). 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 la CPU de una sola máquina para la etapa final 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 que se encuentra en Internet; Esto eventualmente llevó a que Texas Instruments firmara una controversia clave .
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 principal principal 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 [ se necesita aclaración ] mediante el algoritmo de Shor es 21, que se factorizó en 2012. [23] Varios laboratorios habían factorizado previamente 15.
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 el experimento de 2012, de hecho, también había factorizado números mucho mayores sin saberlo. [ se necesita aclaración ] [25] [26] En abril de 2016, el número 200,099 de 18 bits 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 temperatura superior a la ambiente. [28] A finales de 2019, la computación de Zapata 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 incorporar problemas de factorización prima en recocidos cuánticos, lo que llevó a (i) la incorporación de problemas de factorización prima de 21 × 12 en una arquitectura D-Wave Pegasus; (ii) el factoraje 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 de la computación clásica 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 , requiriendo solo 3, 1 y 1 iteración del ciclo respectivamente.
{{cite web}}: Mantenimiento CS1: copia archivada como título ( enlace ){{cite web}}: Mantenimiento CS1: copia archivada como título ( enlace )