stringtranslate.com

factorización de enteros

Problema no resuelto en informática :

¿Se puede resolver la factorización de números enteros en tiempo polinómico en una computadora clásica?

(más problemas sin resolver en informática)

En teoría de números , la factorización de números enteros es la descomposición de un número entero positivo en un producto de números enteros. Todo número entero positivo mayor que 1 es producto de dos o más factores enteros , en cuyo caso se llama número compuesto , o no lo es, en cuyo caso se llama número primo . Por ejemplo, 15 es un número compuesto porque 15 = 3 · 5 , pero 7 es un número primo porque no se puede descomponer de esta manera. Si uno de los factores es compuesto, a su vez se puede escribir como producto de factores más pequeños, por ejemplo 60 = 3 · 20 = 3 · (5 · 4) . Continuar este proceso hasta que cada factor sea primo se llama factorización prima ; el resultado es siempre único hasta el orden de los factores según el teorema de factorización prima .

Para factorizar un número entero pequeño n usando aritmética mental o con lápiz y papel, el método más simple es la división de prueba : verificar si el número es divisible por números primos 2 , 3 , 5 , etc., hasta la raíz cuadrada de n . Para números más grandes, especialmente cuando se usa una computadora, varios algoritmos de factorización más sofisticados son más eficientes. Un algoritmo de factorización prima generalmente implica probar si cada factor es primo cada vez que se encuentra un factor.

Cuando los números son suficientemente grandes, no se conoce ningún algoritmo eficiente de factorización de enteros no cuánticos . Sin embargo, no se ha demostrado que tal algoritmo no exista. La presunta dificultad de este problema es importante para los algoritmos utilizados en criptografía , como el cifrado de clave pública RSA y la firma digital RSA . [1] Muchas áreas de las matemáticas y la informática se han aplicado al 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 de más de dos mil bits de longitud, elegidos al azar y aproximadamente del mismo tamaño (pero no demasiado cercanos, por ejemplo, para evitar una factorización eficiente mediante el método de factorización de Fermat ), incluso los algoritmos de factorización de primos más rápidos del sistema las computadoras más rápidas pueden tardar suficiente tiempo como para que la búsqueda resulte poco práctica; es decir, a medida que aumenta el número de dígitos del número entero que se factoriza, 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 en un problema relacionado (por ejemplo, el problema RSA ). Un algoritmo que factorice eficientemente un número entero arbitrario haría insegura la criptografía de clave pública basada en RSA .

Descomposición prima

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

Según el teorema fundamental de la aritmética , cada número 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 polinómico , por ejemplo, mediante la prueba de primalidad de AKS . Sin embargo, si son compuestos, las pruebas de tiempo polinomiales no dan idea de cómo obtener los factores.

Dado un algoritmo general para la factorización de números enteros, cualquier número entero puede descomponerse 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 lograrse tan bien o incluso no lograrse 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 necesitará p divisiones para encontrar el siguiente factor. Como ejemplo contrastante, si n es 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 ⌈ √ n ⌉ = 18848997159 , lo que inmediatamente produce b = √ un 2 − norte = √ 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 de ⌈ √ 18848997157 ⌉ = 137292 para a es un factor de 10 de 1372933 .

Estado actual del arte

Entre los números de b bits, los más difíciles de factorizar en la práctica utilizando los algoritmos existentes son aquellos semiprimos cuyos factores son de tamaño similar. Por este motivo, estos son los números enteros que se utilizan en las aplicaciones criptográficas.

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. [2] Los investigadores estimaron que un módulo RSA de 1024 bits tardaría aproximadamente 500 veces más. [3]

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 centrales de cálculo con 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

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

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

Para las computadoras actuales, GNFS es el algoritmo mejor publicado para n grande (más de 400 bits). Para una computadora cuántica , sin embargo, Peter Shor descubrió en 1994 un algoritmo que lo resuelve en tiempo polinomial. Esto tendrá importantes implicaciones 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 sobre moléculas que proporcionan siete qubits. [8]

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 además de 1?). Se sabe que está tanto en NP como en co-NP , lo que significa que tanto las respuestas "sí" como las "no" pueden verificarse en tiempo polinomial. Una respuesta "sí" puede certificarse exhibiendo una factorización n = d (norte/d) con re ≤ k . Se puede certificar una respuesta "no" exhibiendo la factorización de n en distintos números primos, todos mayores que k ; se puede verificar su primalidad utilizando la prueba de primalidad de AKS y luego multiplicarlos para obtener n . El teorema fundamental de la aritmética garantiza que sólo habrá una posible cadena de números primos crecientes que será aceptada, lo que demuestra que el problema está tanto en UP como en co-UP. [9] 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-completa y co-NP-completa . 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 ambas clases.

Por el contrario, el problema de decisión "¿Es n un número compuesto?" (o equivalentemente: "¿Es n 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 polinómico (en el número b de dígitos de n ) con la prueba de primalidad de 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 cada vez más pequeña. La facilidad de las pruebas de primalidad es una parte crucial del algoritmo RSA , ya que para empezar es necesario encontrar números primos grandes.

Algoritmos de factorización

Proposito especial

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. [10] Por ejemplo, la división de prueba ingenua es un algoritmo de Categoría 1.

Propósito general

Un algoritmo de factorización de propósito general, también conocido como algoritmo de Categoría 2 , Segunda Categoría o familia Kraitchik , [10] 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 .

Otros algoritmos notables

Tiempo de ejecución heurístico

En teoría de números, existen muchos algoritmos de factorización de números enteros que heurísticamente tienen un tiempo de ejecución esperado.

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

Tiempo de ejecución riguroso

Lenstra y Pomerance [14] han demostrado rigurosamente que el algoritmo probabilístico de Schnorr-Seysen-Lenstra tiene un tiempo de ejecución esperado L n [1/2, 1+ o (1)] reemplazando 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 ternas de números enteros ( a , b , c ) en el que esos números enteros son primos relativos.

Algoritmo de Schnorr-Seysen-Lenstra

Dado un número entero n que será factorizado, 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 se puede restringir a un conjunto pequeño para garantizar el resultado de suavidad.

Denotemos por P Δ el conjunto de todos los primos q con símbolo de Kronecker (Δ/q) = 1 . 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 c 0 (log| Δ |) 2 para alguna constante c 0 .

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 llamada forma ambigua de G Δ , que es un elemento de G Δ de orden que divide a 2. Al calcular la factorización correspondiente de Δ y tomar 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 entero negativo con Δ = − dn , donde d es un multiplicador y Δ es el discriminante negativo de alguna forma cuadrática.
  2. Tome los t primeros primos p 1 = 2, p 2 = 3, p 3 = 5, ..., p t , para algunos t ∈ N .
  3. Sea f q una forma prima aleatoria de G Δ con (Δ/q) = 1 .
  4. Encuentre un conjunto generador X de G Δ .
  5. Reúna una secuencia de relaciones entre el conjunto X y { f q  : q ∈ P Δ } que satisfaga:
  6. Construya una forma ambigua ( a , b , c ) que sea un elemento f ∈ G Δ de orden dividiendo 2 para obtener una factorización coprima del mayor divisor impar de Δ en el que Δ = −4 ac o Δ = a ( a − 4 c ) o Δ = ( segundo - 2 una )( segundo + 2 una ) .
  7. Si la forma ambigua proporciona una factorización de n , entonces 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 número entero positivo, es necesario agregar algunos pasos a este algoritmo, como la división de prueba y la prueba de la suma de Jacobi .

Tiempo de ejecución esperado

El algoritmo indicado es un algoritmo probabilístico ya que toma decisiones aleatorias. Su tiempo de ejecución esperado es como máximo L n [1/2, 1+ o (1)] . [14]

Ver también

Notas

  1. ^ Lenstra, Arjen K. (2011), "Factoring de enteros", en van Tilborg, Henk CA; Jajodia, Sushil (eds.), Enciclopedia de criptografía y seguridad , Boston, MA: Springer US, págs. 611–618, doi :10.1007/978-1-4419-5906-5_455, ISBN 978-1-4419-5905-8, recuperado el 22 de junio de 2022
  2. ^ "[Cado-nfs-discuss] Factorización de 795 bits y logaritmos discretos". Archivado desde el original el 2 de diciembre de 2019.
  3. ^ Kleinjung; et al. (2010-02-18). «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}}: Citar diario requiere |journal=( ayuda )
  4. ^ Krantz, Steven G. (2011), La prueba está en el pudín: la naturaleza cambiante de la prueba matemática, Nueva York: Springer, p. 203, doi :10.1007/978-0-387-48744-1, ISBN 978-0-387-48908-7, señor  2789493
  5. ^ Arora, Sanjeev ; Barak, Boaz (2009), Complejidad computacional, Cambridge: Cambridge University Press, p. 230, doi :10.1017/CBO9780511804090, ISBN 978-0-521-42426-4, SEÑOR  2500087, S2CID  215746906
  6. ^ Goldreich, Oded ; Wigderson, Avi (2008), "IV.20 Complejidad computacional", 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, señor  2467561. Véase en particular la pág. 583.
  7. ^ Bühler, JP; Lenstra, HW Jr.; Pomerancia, Carl (1993). "Factorizar números enteros con el tamiz de campos numéricos". El desarrollo del tamiz de campo numérico. Apuntes de conferencias de matemáticas. vol. 1554. Saltador. págs. 50–94. doi :10.1007/BFb0091539. hdl : 1887/2149. ISBN 978-3-540-57013-4. Consultado el 12 de marzo de 2021 .
  8. ^ 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 Bib :2001Natur.414..883V. doi :10.1038/414883a. PMID  11780055. S2CID  4400832.
  9. ^ Lance Fortnow (13 de septiembre de 2002). "Blog de Complejidad Computacional: Clase de Complejidad de la Semana: Factorización".
  10. ^ ab David Bressoud y Stan Wagon (2000). Un curso de teoría computacional de números . Publicaciones universitarias clave/Springer. págs. 168–69. ISBN 978-1-930190-10-8.
  11. ^ 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. Archivado desde el original el 24 de septiembre de 2017.
  12. ^ Seysen, Martín (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.
  13. ^ Lenstra, Arjen K (1988). «Factorización rápida y rigurosa bajo la hipótesis de Riemann generalizada» (PDF) . Indagaciones Mathematicae . 50 (4): 443–454. doi :10.1016/S1385-7258(88)80022-2.
  14. ^ ab Lenstra, HW; Pomerance, Carl (julio de 1992). "Un plazo riguroso para factorizar números 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

enlaces externos