Factorización de enteros

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 los números primos, el proceso se denomina descomposición en factores primos.

Cuando los números son lo suficientemente grandes, no se conoce ningún algoritmo eficiente de factorización de enteros no cuánticos. Sin embargo, no se ha probado que tal algoritmo no exista. La supuesta 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. 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.

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

No todos los números de una determinada longitud 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 largo, elegidos al azar y aproximadamente del mismo tamaño (pero no demasiado cerca, por ejemplo, para evitar la factorización eficiente por el método de factorización de Fermat), incluso el primo más rápido los algoritmos de factorización en las computadoras más rápidas pueden tomar suficiente tiempo para hacer que la búsqueda no sea práctica; es decir, a medida que aumenta la cantidad de dígitos de los números primos que se factorizan, la cantidad de operaciones requeridas para realizar la factorización en cualquier computadora aumenta drásticamente.

Muchos protocolos criptográficos se basan en la dificultad de factorizar 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

Primera descomposición n = 864 como 2⁵ × 3³

De acuerdo con el teorema fundamental de la aritmética, todo número entero positivo tiene una descomposición en factores primos ú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 compuestas, las pruebas de tiempo polinomial no dan una idea de cómo obtener los factores.

Dado un algoritmo general para la factorización de entero, cualquier entero puede ser factorizado en sus factores principales constituyentes mediante la aplicación repetida de este algoritmo. La situación es más complicada con algoritmos de factorización para fines especiales, cuyos beneficios pueden no realizarse también o incluso en absoluto con los factores producidos durante la descomposición. Por ejemplo, si n = 171 × p × q Donde p. q son grandes primas, 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 n es el producto de los primos 13729, 1372933, y 18848997161, donde 13729 × 1372933 = 18848997157, el método de factorización de Fermat comenzará con ⌈ ⌈ n⌉ ⌉ =18848997159{displaystyle lceil {sqrt {n}rceil =18848997159} que cede inmediatamente b=a2− − n=4=2b{textstyle b={sqrt {a}-n}={sqrt {4}=2b} y, por consiguiente, los factores a − b = 18848997157 y a + b = 18848997161. Aunque estos son fácilmente reconocidos como compuestos y primos respectivamente, el método de Fermat tardará mucho más en tener en cuenta el número compuesto porque el valor inicial de ⌈ ⌈ 18848997157⌉ ⌉ =137292{textstyle lceil {sqrt {18848997157}rceil =137292} para a no está cerca de 1372933.

Estado actual del arte

Entre los números de b bits, los más difíciles de factorizar en la práctica usando los 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 semiprime 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 de cálculo total fue de aproximadamente 2700 años de núcleo de computación con Intel Xeon Gold 6130 a 2,1 GHz. Al igual que todos los registros de factorización recientes, esta factorización se completó con una implementación altamente optimizada de la corrida de tamiz de campo numérico general en cientos de máquinas.

Dificultad y complejidad

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

Hay algoritmos publicados que son más rápidos que O((1 + ε)^b) para todos los ε, es decir, subexponencial. A partir de 2022, 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, que se ejecuta en un número b de bits n en hora:

exp⁡ ⁡ ()()6493+o()1))()In⁡ ⁡ n)13()In⁡ ⁡ In⁡ ⁡ n)23).{displaystyle expleft(sqrt[{3}{frac {64}{9}}+o(1)right)(ln n)^{frac {1}{3}}(lnln n)^{frac {2}{3}}right). }

Para las computadoras actuales, GNFS es el mejor algoritmo publicado para grandes n (más de 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 tiempo O(b³) y espacio O(b) en b -entradas de número de bits. En 2001 se implementó por primera vez el algoritmo de Shor, utilizando técnicas de RMN sobre moléculas que proporcionan 7 qubits.

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 "sí" y "no" Las respuestas se pueden verificar en tiempo polinomial. Una respuesta de "sí" se puede certificar exhibiendo una factorización n = d(n/d) con d ≤ k. Una respuesta de "no" se puede certificar exhibiendo la factorización de n en números primos distintos, todos mayores que k; uno puede verificar su primalidad utilizando la prueba de primalidad AKS y luego multiplicarlos para obtener n. El teorema fundamental de la aritmética garantiza que solo se aceptará una cadena posible de números primos crecientes, lo que demuestra que el problema está tanto en UP como en co-UP. 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 que 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.

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

Algoritmos de factorización

Propósito especial

El tiempo de ejecución de un algoritmo de factorización de propósito especial depende de las propiedades del número que se va 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 los 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. Por ejemplo, la división de prueba ingenua es un algoritmo de categoría 1.

• División de Primera Instancia
• Factorización de la rueda
• El algoritmo rho de Pollard, que tiene dos sabores comunes para identificar ciclos de grupo: uno por Floyd y uno por Brent.
• algoritmos de factorización de grupo algebraico, entre los cuales se encuentran el algoritmo p - 1 de Pollard, algoritmo de Williams p + 1 y factorización de curva elíptica Lenstra
• Método de factorización de Fermat
• Método de factorización de Euler
• Número especial de sieve de campo

Propósito general

Un algoritmo de factorización de propósito general, también conocido como algoritmo Categoría 2, Segunda categoría o familia de Kraitchik, tiene un tiempo de ejecución que depende únicamente del tamaño del entero 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 de la fracción continua (CFRAC)
• Sieve cuadrática
• Sieve racional
• Número general de sieve
• Factorización de las formas cuadradas de Shanks (SQUFOF)

Otros algoritmos destacados

• Algoritmo de Shor, para computadoras cuánticas

Tiempo de ejecución heurístico

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

Ln[12,1+o()1)]=e()1+o()1))()log⁡ ⁡ n)()log⁡ ⁡ log⁡ ⁡ n){displaystyle L_{n}left[{tfrac {1}{2},1+o(1)right]=e^{(1+o(1)){sqrt {(log n)(log log n)}}}}}

en notación minúscula y L. Algunos ejemplos de esos algoritmos son el método de la curva elíptica y el tamiz cuadrático. Otro algoritmo de este tipo es el método de relaciones de grupo de clase propuesto por Schnorr, Seysen y Lenstra, que probaron solo asumiendo la Hipótesis de Riemann Generalizada (GRH) no probada.

Tiempo de ejecución riguroso

El algoritmo probabilístico de Schnorr-Seysen-Lenstra ha sido rigurosamente demostrado por Lenstra y Pomerance de haber esperado tiempo de funcionamiento Ln[12,1+o()1)]{displaystyle L_{n}left [{tfrac {1}{2},1+o(1)right]} sustituyendo el supuesto GRH por el uso de multiplicadores. El algoritmo utiliza el grupo de clase de formas cuadráticas binarias positivas de discriminación Δ denotado por G_Δ. G_Δ es el conjunto de triples de enteros (a, b, c) en que esos enteros son primos relativos.

Algoritmo de Schnorr-Seysen-Lenstra

Dado un entero n que será factorizado, donde n es un entero positivo impar mayor que cierta constante. En este algoritmo de factorización, el discriminante Δ se elige como múltiplo de n, Δ = −dn, donde d es un multiplicador positivo. El algoritmo espera que para una 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 by P_Δ el conjunto de todos los primos q con el símbolo Kronecker ()Δ Δ q)=1{displaystyle left({tfrac {Delta}{q}right)=1}. Construyendo un conjunto de generadores de G_Δ y formas primo f_q de G_Δ con q dentro P_Δ una secuencia de relaciones entre el conjunto de generadores y f_q son producidos. El tamaño de q puede ser obligado por c0()log⁡ ⁡ SilencioΔ Δ Silencio)2{displaystyle c_{0} Silencio. para alguna constante c0{displaystyle 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 2. Al calcular la factorización correspondiente de Δ y al 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. Dejar Δ ser un entero negativo con Δ = −♪, donde d es un multiplicador y Δ es el discriminante negativo de alguna forma cuadrática.
2. Toma. t primos p1=2,p2=3,p3=5,...... ,pt{displaystyle p_{1}=2,p_{2}=3,p_{3}=5,dotsp_{t}, para algunos t▪ ▪ N{displaystyle tin {fnMithbb {N}.
3. Vamos fq{displaystyle f_{q} ser una forma original aleatoria G_Δ con ()Δ Δ q)=1{displaystyle left({tfrac {Delta}{q}right)=1}.
4. Encontrar un conjunto generador X de G_Δ
5. Recoger una secuencia de relaciones entre conjunto X y {}f_q: q ▪ P_ΔSatisfacción: ()∏ ∏ x▪ ▪ Xxr()x)).()∏ ∏ q▪ ▪ PΔ Δ fqt()q))=1{displaystyle left(prod _{xin X_{}x^{r(x)}right).left(prod _{qin P_{Delta }f_{q}{t(q)}right)=1}
6. Construir una forma ambigua ()a,b,c){displaystyle (a,b,c)} que es un elemento f ▪ G_Δ de orden dividiendo 2 para obtener una factorización coprime del mayor divisor extraño de Δ en el cual Δ Δ =− − 4acoa()a− − 4c)o()b− − 2a)()b+2a){displaystyle Delta =-4ac{text{ or }a(a-4c){text{ or }(b-2a)(b+2a)}
7. Si la forma ambigua proporciona una factorización n entonces parar, de otro modo encontrar otra forma ambigua hasta la factorización n se encuentra. Para evitar que las formas ambiguas inútiles generen, construyan el grupo 2-Sylow₂(Δ) of 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 funcionamiento esperado

El algoritmo como se indica es un algoritmo probabilístico ya que toma decisiones aleatorias. Su tiempo de funcionamiento esperado es como mucho Ln[12,1+o()1)]{displaystyle L_{n}left [{tfrac {1}{2},1+o(1)right]}.