La factorización de enteros es el proceso de determinar qué números primos dividen 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 semiprimes grandes (y, de hecho, la mayoría de los números que no tienen factores pequeños).
Números de una forma general
La primera factorización enorme distribuida fue RSA-129 , un número de desafío 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 las 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 preparado por la empresa RSA, se factorizó utilizando GNFS con relaciones nuevamente aportadas por un gran grupo, 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 Académico de Computación 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 clúster de seis PC Pentium-III.
En abril de 2003, el mismo equipo factorizó RSA-160 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 fue factorizado por Franke, Kleinjung y miembros de la colaboración NFSNET en diciembre de 2003, utilizando recursos en 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 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] Posteriormente (noviembre de 2005) factorizaron el número de desafío RSA-640 ligeramente menor .
El 12 de diciembre de 2009, un equipo que incluía investigadores del CWI , EPFL , INRIA y NTT, además de los autores del registro anterior, factorizó RSA-768 , un semiprimo de 232 dígitos. [3] Usaron el equivalente a casi 2000 años de computación en un procesador AMD Opteron de 2,2 GHz de un solo núcleo .
En noviembre de 2019, el RSA-240 de 795 bits fue factorizado por Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé y Paul Zimmermann. [4] [5]
En febrero de 2020, se completó la factorización del RSA-250 de 829 bits . [6]
Números de una forma especial
12 151 - 1, de 542 bits (163 dígitos), se tuvo en cuenta, entre abril y julio de 1993 por un equipo de la CIT y la Universidad Estatal de Oregón . [7]
2 773 + 1, de 774 bits (233 dígitos), se tuvo en cuenta, entre abril y noviembre de 2000 por 'El Cabal', con la etapa de matriz de hecho más de 250 horas en el Cray también utilizados para RSA-155. [8]
2 809 - 1, de 809 bits (244 dígitos), tuvo su factorización anunciado al inicio de enero de 2003. El tamizado se realizó en el CIT, en el Instituto de Computación Científica y el Departamento de Matemática Pura en la Universidad de Bonn, y el uso de 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 Amsterdam. [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, usando 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 encabezado por Greg Childers en CSU Fullerton, utilizando el proyecto BOINC nfs @ home para aproximadamente 300 CPU-años de tamizado; el álgebra lineal se ejecutó en el grupo Trestles en SDSC y el grupo Lonestar en TACC y necesitó 35 años de CPU adicionales. [13]
Todas las partes no factorizadas de los números 2 n - 1 con n entre 1000 y 1200 se factorizaron 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 varios números, por un grupo que incluye a T. Kleinjung, J Bos y AK Lenstra , a partir de 2010. [14] Para ser precisos, n = 1081 se completó el 11 de marzo de 2013; n = 1111 el 13 de junio de 2013; n = 1129 el 20 de septiembre de 2013; n = 1153 el 28 de octubre de 2013; n = 1159 el 9 de febrero de 2014; 1177 el 29 de mayo de 2014, n = 1193 el 22 de agosto de 2014 y n = 1199 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 CPU-años en Opterons de 2,2 GHz, con aproximadamente 5700 años de tamizado y 1800 años de álgebra lineal.
Comparación con los esfuerzos de los individuos
A finales de 2007, gracias a la constante disminución de los precios de la memoria, la disponibilidad inmediata de ordenadores de 64 bits con varios núcleos y la disponibilidad del código de tamizado eficiente (desarrollado por Thorsten Kleinjung del grupo Bonn) a través de ggnfs [15 ] y de un software robusto de código abierto como msieve [16] para las etapas de acabado, los números de forma especial de hasta 750 bits y los números de forma general de hasta aproximadamente 520 bits se pueden factorizar en unos pocos meses en unas pocas PC por una sola persona sin ninguna experiencia matemática especial. [17] Estos límites aumentan a aproximadamente 950 [18] y 600 [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 de acabado son barreras iguales para el progreso.
En 2009, Benjamin Moody factorizó una clave RSA de 512 bits utilizada para firmar la calculadora gráfica TI-83 utilizando software que se encuentra en Internet; esto eventualmente llevó a la controversia clave de firma de Texas Instruments .
En septiembre de 2013, Ryan Propper [20] factorizó el RSA-210 de 696 bits utilizando recursos institucionales; entre marzo de 2013 y octubre de 2014, un usuario conocido como WraithX completó otro número de 210 dígitos (el término 117 en la 'secuencia principal de inicio' que comienza con 49), [21] 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.
Registros de esfuerzos de computadoras cuánticas
El número más grande factorizado de forma fiable por el algoritmo de Shor es 21, que se factorizó en 2012. [23] 15 habían sido factorizados anteriormente por varios laboratorios.
En abril de 2012, la factorización de por un equipo cuántico adiabático de RMN a temperatura ambiente (300K) fue informado por un grupo dirigido por Xinhua Peng. [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. [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, 291 311 se factorizó utilizando RMN a una temperatura superior a la ambiente. [28] A fines de 2019, una colaboración de la industria encontró que 1.099.551.473.989 es igual a 1.048.589 multiplicado por 1.048.601. [29]
Ver también
- Número primo más grande conocido
Referencias
- ^ K. Aoki; Y. Kida; T. Shimoyama; H. Ueda. "Factorización de número de 176 dígitos" . Consultado el 23 de mayo de 2007 .
- ^ F. Bahr; M. Boehm; J. Franke; T. Kleinjung. "RSA200" . Consultado el 23 de mayo de 2007 .
- ^ T. Kleinjung; K. Aoki; J. Franke; AK Lenstra; E. Thomé; JW Bos; P. Gaudry; A. Kruppa; PL Montgomery; DA Osvik; H. te Riele; A. Timofeev; P. Zimmermann. "Factorización de un módulo RSA de 768 bits" (PDF) . Consultado el 11 de abril de 2013 .
- ^ https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2019-December/001139.html
- ^ F. Boudot et al, "Comparación de la dificultad de la factorización y el logaritmo discreto: un experimento de 240 dígitos" , 10 de junio de 2020.
- ^ https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;dc42ccd1.2002
- ^ PL Montgomery. "Factorizaciones de tamices de campo con número de registro" . Consultado el 23 de noviembre de 2007 .
- ^ 'El Cabal'. "Factorización SNFS de 233 dígitos" . Archivado desde el original el 28 de noviembre de 2007 . Consultado el 23 de noviembre de 2007 .
- ^ J. Franke. "M809" . Archivado desde el original el 23 de agosto de 2007 . Consultado el 23 de noviembre de 2007 .
- ^ K. Aoki; Y. Kida; T. Shimoyama; H. Ueda. "SNFS274" . Consultado el 23 de mayo de 2007 .
- ^ K. Aoki; J. Franke; T. Kleinjung; AK Lenstra; DA Osvik. "Factorización del número 1039 de Mersenne" . Consultado el 23 de mayo de 2007 .
- ^ Kazumaro Aoki; Jens Franke; Thorsten Kleinjung; Arjen Lenstra; Dag Arne Osvik. "Una factorización de tamiz de campo de número especial de kilobits" . Consultado el 19 de diciembre de 2007 .
- ^ Greg Childers. "Factorización de un número de 1061 bits por el tamiz de campo de número especial" .
- ^ Thorsten Kleinjung; Joppe W Bos; Arjen K. Lenstra. "Fábrica de factorización de Mersenne" . Consultado el 18 de enero de 2015 .
- ^ "Suite GGNFS - Examinar archivos en SourceForge.net" . sourceforge.net .
- ^ "Copia archivada" . Archivado desde el original el 13 de diciembre de 2007 . Consultado el 23 de noviembre de 2007 .CS1 maint: copia archivada como título ( enlace )
- ^ "mersenneforum.org - Ver publicación única - Tabla 2LM" . www.mersenneforum.org .
- ^ "mersenneforum.org - Ver publicación única - Un cálculo digno de ese nombre" . www.mersenneforum.org .
- ^ "mersenneforum.org - Ver publicación única - tamizado 5 ^ 421-1 (reservas cerradas)" . www.mersenneforum.org .
- ^ "RSA-210 factorizado - mersenneforum.org" . mersenneforum.org .
- ^ "mersenneforum.org - Ver publicación única - HP49 (119) ..." www.mersenneforum.org .
- ^ https://mersenneforum.org/showpost.php?p=389078&postcount=105
- ^ Martín-López, Enrique; Enrique Martín-López; Anthony Laing; Thomas Lawson; Roberto Alvarez; Xiao-Qi Zhou; Jeremy L. O'Brien (12 de octubre de 2012). "Realización experimental del algoritmo de factorización cuántica de Shor utilizando reciclaje de qubit". Nature Photonics . 6 (11): 773. arXiv : 1111.4147 . Código Bibliográfico : 2012NaPho ... 6..773M . doi : 10.1038 / nphoton.2012.259 .
- ^ "143 es el número más grande que aún no ha sido factorizado por un algoritmo cuántico" .
- ^ "El nuevo número más grande factorizado en un dispositivo cuántico es 56.153" .
- ^ "El truco matemático que ayudó a romper el récord del número más grande jamás factorizado por un ..." 2 de diciembre de 2014.
- ^ Dridi, Raouf; Alghassi, Hedayat (21 de febrero de 2017). "Factorización prima mediante recocido cuántico y geometría algebraica computacional" . Informes científicos . 7 : 43048. arXiv : 1604.05796 . Código Bib : 2017NatSR ... 743048D . doi : 10.1038 / srep43048 . PMC 5318873 . PMID 28220854 .
- ^ Li, Zhaokai; Dattani, Nike; Chen, Xi; Liu, Xiaomei; Wang, Hengyan; Tanburn, Richard; Chen, Hongwei; Peng, Xinhua; Du, Jiangfeng (25 de junio de 2017). "Computación cuántica adiabática de alta fidelidad utilizando el hamiltoniano intrínseco de un sistema de espín: aplicación a la factorización experimental de 291311". arXiv : 1706.08061 [ quant-ph ].
- ^ Crane, Leah. "La computadora cuántica establece un nuevo récord para encontrar factores de números primos" . Nuevo científico . Consultado el 2 de octubre de 2020 .