De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda
Problema no resuelto en informática :

¿Se puede resolver la factorización de enteros en tiempo polinomial en una computadora clásica?

En teoría de números , la factorización de enteros es la descomposición de un número compuesto en un producto de números enteros más pequeños. Si estos factores se restringen aún más a números primos , el proceso se denomina factorización prima .

Cuando los números son lo suficientemente grandes, no se conoce ningún algoritmo de factorización de enteros no cuántico eficiente . En 2019, Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé y Paul Zimmermann factorizaron un número de 240 dígitos (795 bits) ( RSA-240 ) utilizando aproximadamente 900 años centrales de potencia informática. [1] Los investigadores estimaron que un módulo RSA de 1024 bits tardaría unas 500 veces más. [2] Sin embargo, no se ha demostrado que no exista un algoritmo eficiente. La presunta dificultad de este problema está en el corazón de los algoritmos ampliamente utilizados en criptografía como RSA . Muchas áreas de las matemáticas y las ciencias de la computación se han involucrado en el problema, incluidas las curvas elípticas , la teoría algebraica de números y la computación cuántica .

No todos los números de una longitud determinada son igualmente difíciles de factorizar. Los casos más difíciles de estos problemas (para las técnicas actualmente conocidas) son los semiprimos , el producto de dos números primos. Cuando ambos son grandes, por ejemplo, más de dos mil bits de longitud, elegidos aleatoriamente y aproximadamente del mismo tamaño (pero no demasiado cerca, por ejemplo, para evitar una factorización eficiente mediante el método de factorización de Fermat ), incluso los algoritmos de factorización prima más rápidos en el las computadoras más rápidas pueden tardar el tiempo suficiente para que la búsqueda no sea práctica; es decir, a medida que aumenta el número de dígitos de los números primos factorizados, el número de operaciones necesarias para realizar la factorización en cualquier computadora aumenta drásticamente.

Muchos protocolos criptográficos se basan en la dificultad de factorizar números enteros compuestos grandes o un problema relacionado, por ejemplo, el problema RSA . Un algoritmo que factoriza eficientemente un entero arbitrario haría insegura la criptografía de clave pública basada en RSA .

Descomposición prima [ editar ]

Descomposición prima de n = 864 como 2 5 × 3 3

Según el teorema fundamental de la aritmética , todo entero positivo tiene una factorización prima única . (Por convención, 1 es el producto vacío ). La prueba de si el número entero es primo se puede realizar en tiempo polinomial , por ejemplo, mediante la prueba de primalidad AKS . Sin embargo, si son compuestos, las pruebas de tiempo polinomial no dan una idea de cómo obtener los factores.

Dado un algoritmo general para la factorización de números enteros, cualquier número entero se puede factorizar en sus factores primos constituyentes mediante la aplicación repetida de este algoritmo. La situación es más complicada con los algoritmos de factorización de propósito especial, cuyos beneficios pueden no realizarse tan bien o incluso en absoluto con los factores producidos durante la descomposición. Por ejemplo, si n = 171 × p × q donde p < q son números primos muy grandes, la división de prueba producirá rápidamente los factores 3 y 19, pero tomará p divisiones para encontrar el siguiente factor. Como ejemplo contrastante, si nes el producto de los números primos 13729, 1372933 y 18848997161, donde 13729 × 1372933 = 18848997157 , el método de factorización de Fermat comenzará con a = ⌈ n ⌉ = 18848997159 que inmediatamente da b = a 2 - n = 4 = 2 y de ahí los factores a - b = 18848997157 y a + b = 18848997161 . Si bien estos se reconocen fácilmente como compuestos y primos respectivamente, el método de Fermat tomará mucho más tiempo para factorizar el número compuesto porque el valor inicial de18848997157 ⌉ = 137292 para a no está cerca de 1372933.

Estado actual de la técnica [ editar ]

Entre los números de b bits, los más difíciles de factorizar en la práctica utilizando algoritmos existentes son aquellos que son productos de dos números primos de tamaño similar. Por esta razón, estos son los números enteros que se utilizan en las aplicaciones criptográficas. El semiprimo más grande hasta ahora factorizado fue RSA-250 , un número de 829 bits con 250 dígitos decimales, en febrero de 2020. El tiempo total de cálculo fue de aproximadamente 2700 años-núcleo de computación utilizando Intel Xeon Gold 6130 a 2,1 GHz. Como todos los registros de factorización recientes, esta factorización se completó con una implementación altamente optimizada del tamiz de campo numérico general ejecutado en cientos de máquinas.

Dificultad y complejidad [ editar ]

No se ha publicado ningún algoritmo que pueda factorizar todos los números enteros en el tiempo polinomial , es decir, que pueda factorizar un número de b bits n en el tiempo O ( b k ) para alguna constante k . No se ha demostrado ni la existencia ni la inexistencia de tales algoritmos, pero generalmente se sospecha que no existen y, por lo tanto, el problema no está en la clase P. [3] [4] El problema está claramente en la clase NP, pero generalmente se sospecha que no es NP-completo , aunque esto no ha sido probado. [5]

Hay algoritmos publicados que son más rápidos que O ((1 +  ε ) b ) para todos los ε positivos , es decir, sub-exponenciales . A partir del 2021-03-12, el algoritmo con el mejor tiempo de ejecución asintótico teórico es el tamiz de campo numérico general ( GNFS ), publicado por primera vez en 1993, [6] que se ejecuta en un número n de bits b en el tiempo.

Para las computadoras actuales, GNFS es el mejor algoritmo publicado para n grandes (más de unos 400 bits). Sin embargo, para una computadora cuántica , Peter Shor descubrió un algoritmo en 1994 que lo resuelve en tiempo polinomial. Esto tendrá implicaciones significativas para la criptografía si la computación cuántica se vuelve escalable. El algoritmo de Shor toma solo O ( b 3 ) tiempo y O ( b ) espacio en entradas de números de b bits. En 2001, se implementó por primera vez el algoritmo de Shor, utilizando técnicas de RMN en moléculas que proporcionan 7 qubits. [7]

No se sabe exactamente qué clases de complejidad contienen la versión de decisión del problema de factorización de enteros (es decir: ¿ n tiene un factor menor que k ?). Se sabe que está tanto en NP como en co-NP , lo que significa que tanto las respuestas "sí" como las "no" se pueden verificar en tiempo polinomial. Una respuesta "sí" puede certificarse exhibiendo una factorización n = d ( n / d ) con dk . Una respuesta de "no" se puede certificar exhibiendo la factorización de n en distintos números primos, todos mayores que k; uno puede verificar su primalidad usando la prueba de primalidad AKS , y luego multiplicarlos para obtener n . El teorema fundamental de la aritmética garantiza que solo hay una cadena posible de primos crecientes que serán aceptados, lo que muestra que el problema está tanto en UP como en co-UP. [8] Se sabe que está en BQP debido al algoritmo de Shor.

Se sospecha que el problema está fuera de las tres clases de complejidad P, NP-completo y co-NP-completo . Por lo tanto, es un candidato para la clase de complejidad intermedia NP . Si se pudiera demostrar que es NP-completo o co-NP-completo, esto implicaría NP = co-NP, un resultado muy sorprendente y, por lo tanto, se sospecha ampliamente que la factorización de enteros está fuera de estas dos clases. Mucha gente ha intentado encontrar algoritmos clásicos de tiempo polinomial para él y ha fallado, y por lo tanto, se sospecha ampliamente que está fuera de P.

Por el contrario, el problema de decisión "¿Es n un número compuesto?" (o de manera equivalente: "¿ n es un número primo?") parece ser mucho más fácil que el problema de especificar factores de n . El problema compuesto / primo se puede resolver en tiempo polinomial (en el número b de dígitos de n ) con la prueba de primalidad AKS . Además, existen varios algoritmos probabilísticos que pueden probar la primalidad muy rápidamente en la práctica si uno está dispuesto a aceptar una posibilidad de error extremadamente pequeña. La facilidad de las pruebas de primalidad es una parte crucial del algoritmo RSA , ya que es necesario encontrar números primos grandes para empezar.

Factorizar algoritmos [ editar ]

Propósito especial [ editar ]

El tiempo de ejecución de un algoritmo de factorización de propósito especial depende de las propiedades del número a factorizar o de uno de sus factores desconocidos: tamaño, forma especial, etc. Los parámetros que determinan el tiempo de ejecución varían entre algoritmos.

Una subclase importante de algoritmos de factorización de propósito especial son los algoritmos de Categoría 1 o Primera Categoría , cuyo tiempo de ejecución depende del tamaño del factor primo más pequeño. Dado un número entero de forma desconocida, estos métodos generalmente se aplican antes que los métodos de propósito general para eliminar factores pequeños. [9] Por ejemplo, la división de prueba ingenua es un algoritmo de Categoría 1.

  • División de prueba
  • Factorización de ruedas
  • Algoritmo rho de Pollard
  • Algoritmos de factorización de grupos algebraicos , entre los que se encuentran el algoritmo p  - 1 de Pollard , el algoritmo p  + 1 de Williams y la factorización de la curva elíptica de Lenstra
  • Método de factorización de Fermat
  • Método de factorización de Euler
  • Tamiz de campo de número especial

De uso general [ editar ]

Un algoritmo de factorización de propósito general, también conocido como algoritmo de categoría 2 , segunda categoría o familia de Kraitchik , [9] tiene un tiempo de ejecución que depende únicamente del tamaño del número entero que se va a factorizar. Este es el tipo de algoritmo utilizado para factorizar números RSA . La mayoría de los algoritmos de factorización de propósito general se basan en el método de congruencia de cuadrados .

  • El algoritmo de Dixon
  • Factorización continua de fracciones (CFRAC)
  • Tamiz cuadrático
  • Tamiz racional
  • Tamiz de campo de número general
  • Factorización de formas cuadradas de Shanks (SQUFOF)

Otros algoritmos notables [ editar ]

  • Algoritmo de Shor , para computadoras cuánticas

Tiempo de ejecución heurístico [ editar ]

En teoría de números, hay muchos algoritmos de factorización de enteros que heurísticamente han esperado el tiempo de ejecución

en poco-O y L-notación . Algunos ejemplos de esos algoritmos son el método de curva elíptica y el tamiz cuadrático . Otro de estos algoritmos es el método de relaciones de grupo de clases propuesto por Schnorr, [10] Seysen, [11] y Lenstra, [12] que demostraron sólo asumiendo la Hipótesis de Riemann Generalizada (GRH) no probada .

Tiempo de ejecución riguroso [ editar ]

Lenstra y Pomerance [13] han probado rigurosamente que el algoritmo probabilístico de Schnorr-Seysen-Lenstra tiene un tiempo de ejecución esperado al reemplazar el supuesto de GRH con el uso de multiplicadores. El algoritmo utiliza el grupo de clases de formas cuadráticas binarias positivas del discriminante Δ denotado por G Δ .G Δ es el conjunto de triples de números enteros ( a , b , c ) en los que esos números enteros son primos relativos.

Algoritmo de Schnorr-Seysen-Lenstra [ editar ]

Dado un número entero n que se factorizará, donde n es un número entero positivo impar mayor que una determinada constante. En este algoritmo de factorización, el discriminante Δ se elige como un múltiplo de n , Δ = - dn , donde d es un multiplicador positivo. El algoritmo espera que para uno d existan suficientes formas suaves en G Δ . Lenstra y Pomerance muestran que la elección de d puede restringirse a un conjunto pequeño para garantizar el resultado de suavidad.

Denote por P Δ el conjunto de todos los primos q con el símbolo de Kronecker . Al construir un conjunto de generadores de G Δ y formas primas f q de G Δ con q en P Δ se produce una secuencia de relaciones entre el conjunto de generadores y f q . El tamaño de q puede estar acotado por alguna constante .

La relación que se utilizará es una relación entre el producto de potencias que es igual al elemento neutro de G Δ . Estas relaciones se utilizarán para construir la denominada forma ambigua de G Δ , que es un elemento de G Δ de orden dividiendo 2. Calculando la factorización correspondiente de Δ y tomando un mcd , esta forma ambigua proporciona la factorización prima completa. de n . Este algoritmo tiene estos pasos principales:

Sea n el número a factorizar.

  1. Sea Δ un número entero negativo con Δ = - dn , donde d es un multiplicador y Δ es el discriminante negativo de alguna forma cuadrática.
  2. Tome las camisetas primeros números primos , por alguna .
  3. Sea una forma prima aleatoria de G Δ con .
  4. Encuentre un grupo electrógeno X de G Δ
  5. Recopile una secuencia de relaciones entre el conjunto X y { f q  : qP Δ } satisfaciendo:
  6. Construya una forma ambigua que sea un elemento fG Δ de orden dividiendo 2 para obtener una factorización coprima del divisor impar más grande de Δ en la que
  7. Si la forma ambigua proporciona una factorización de n , deténgase; de ​​lo contrario, busque otra forma ambigua hasta encontrar la factorización de n . Para evitar que se generen formas ambiguas inútiles, construya el grupo 2-Sylow Sll 2 (Δ) de G (Δ).

Para obtener un algoritmo para factorizar cualquier entero positivo, es necesario agregar algunos pasos a este algoritmo, como la división de prueba y la prueba de suma de Jacobi .

Tiempo de ejecución esperado [ editar ]

El algoritmo como se indica es un algoritmo probabilístico ya que toma decisiones aleatorias. Su tiempo de ejecución esperado es como máximo . [13]

Ver también [ editar ]

  • Algoritmo de Bach para generar números aleatorios con sus factorizaciones
  • Representación canónica de un entero positivo
  • Factorización
  • Partición multiplicativa
  • Partición (teoría de números) : una forma de escribir un número como una suma de números enteros positivos.

Notas [ editar ]

  1. ^ https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2019-December/001139.html
  2. ^ Kleinjung; et al. (18 de febrero de 2010). "Factorización de un módulo RSA de 768 bits" (PDF) . Asociación Internacional para la Investigación Criptológica . Consultado el 9 de agosto de 2010 . Cite journal requires |journal= (help)
  3. ^ Krantz, Steven G. (2011), The Proof is in the Pudding: The Changing Nature of Mathematical Proof , Nueva York: Springer, p. 203, doi : 10.1007 / 978-0-387-48744-1 , ISBN 978-0-387-48908-7, MR  2789493
  4. ^ Arora, Sanjeev ; Barak, Boaz (2009), Complejidad computacional , Cambridge: Cambridge University Press, p. 230, doi : 10.1017 / CBO9780511804090 , ISBN 978-0-521-42426-4, MR  2500087
  5. ^ Goldreich, Oded ; Wigderson, Avi (2008), "IV.20 Computational Complexity", en Gowers, Timothy ; Barrow-Green, junio ; Líder, Imre (eds.), The Princeton Companion to Mathematics , Princeton, Nueva Jersey: Princeton University Press, págs. 575–604, ISBN 978-0-691-11880-2, MR  2467561. Ver en particular la p. 583 .
  6. ^ Buhler, JP; Lenstra, HW Jr .; Pomerance, Carl (1993). Factorizar enteros con el tamiz de campo numérico (Lecture Notes in Mathematics, vol 1554 ed.). Saltador. págs. 50–94. ISBN 978-3-540-57013-4. Consultado el 12 de marzo de 2021 .
  7. ^ Vandersypen, Lieven MK; et al. (2001). "Realización experimental del algoritmo de factorización cuántica de Shor mediante resonancia magnética nuclear". Naturaleza . 414 (6866): 883–887. arXiv : quant-ph / 0112176 . Código Bibliográfico : 2001Natur.414..883V . doi : 10.1038 / 414883a . PMID 11780055 . S2CID 4400832 .  
  8. Lance Fortnow (13 de septiembre de 2002). "Blog de complejidad computacional: clase de complejidad de la semana: factorización" .
  9. ↑ a b David Bressoud y Stan Wagon (2000). Un curso de teoría de números computacionales . Publicaciones universitarias clave / Springer. págs.  168–69 . ISBN 978-1-930190-10-8.
  10. ^ Schnorr, Claus P. (1982). "Análisis refinado y mejoras en algunos algoritmos de factorización" . Revista de algoritmos . 3 (2): 101-127. doi : 10.1016 / 0196-6774 (82) 90012-8 . Señor 0657269 . 
  11. ^ Seysen, Martin (1987). "Un algoritmo de factorización probabilística con formas cuadráticas de discriminante negativo" . Matemáticas de la Computación . 48 (178): 757–780. doi : 10.1090 / S0025-5718-1987-0878705-X . Señor 0878705 . 
  12. ^ Lenstra, Arjen K (1988). "Factorización rápida y rigurosa bajo la hipótesis de Riemann generalizada". Indagationes Mathematicae . 50 (4): 443–454. doi : 10.1016 / S1385-7258 (88) 80022-2 .
  13. ^ a b Lenstra, HW; Pomerance, Carl (julio de 1992). "Un riguroso límite de tiempo para factorizar enteros" (PDF) . Revista de la Sociedad Matemática Estadounidense . 5 (3): 483–516. doi : 10.1090 / S0894-0347-1992-1137100-0 . Señor 1137100 .  

Referencias [ editar ]

  • Richard Crandall y Carl Pomerance (2001). Números primos: una perspectiva computacional . Saltador. ISBN 0-387-94777-9.Capítulo 5: Algoritmos de factorización exponencial, págs. 191–226. Capítulo 6: Algoritmos de factorización subexponencial, págs. 227–284. Sección 7.4: Método de curva elíptica, págs. 301–313.
  • Donald Knuth . El arte de la programación informática , volumen 2: algoritmos seminuméricos , tercera edición. Addison-Wesley, 1997. ISBN 0-201-89684-2 . Sección 4.5.4: Factorizar en Primes, págs. 379–417. 
  • Samuel S. Wagstaff Jr. (2013). La alegría de la factorización . Providence, RI: Sociedad Matemática Estadounidense. ISBN 978-1-4704-1048-3..
  • Warren Jr., Henry S. (2013). Hacker's Delight (2 ed.). Addison Wesley - Pearson Education, Inc. ISBN 978-0-321-84268-8.

Enlaces externos [ editar ]

  • msieve - SIQS y NFS - ha ayudado a completar algunas de las factorizaciones públicas más grandes conocidas
  • Richard P. Brent, "Progreso reciente y perspectivas de los algoritmos de factorización de enteros", Computación y combinatoria " , 2000, págs. 3–22. Descargar
  • Manindra Agrawal , Neeraj Kayal, Nitin Saxena, "PRIMES está en P." Annals of Mathematics 160 (2): 781-793 (2004). Versión de agosto de 2005 PDF
  • Eric W. Weisstein, “RSA-640 factorizado” MathWorld Headline News , 8 de noviembre de 2005