En matemáticas , 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 el producto de dos o más factores enteros mayores que 1, en cuyo caso se denomina número compuesto , o no lo es, en cuyo caso se denomina 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 un producto de factores más pequeños, por ejemplo 60 = 3 · 20 = 3 · (5 · 4) . Continuar este proceso hasta que todos los factores sean primos se denomina factorización prima ; el resultado siempre es único hasta el orden de los factores según el teorema de factorización prima .
Para factorizar un entero pequeño n mediante aritmética mental o con lápiz y papel, el método más simple es la división por tanteo : comprobar si el número es divisible por los números primos 2 , 3 , 5 , etc., hasta la raíz cuadrada de n . Para números mayores, especialmente cuando se utiliza una computadora, existen varios algoritmos de factorización más sofisticados que son más eficientes. Un algoritmo de factorización prima generalmente implica comprobar 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 números 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 involucrado en el problema, incluidas las curvas elípticas , la teoría de números algebraicos y la computación cuántica .
No todos los números de una longitud dada son igualmente difíciles de factorizar. Los ejemplos más difíciles de estos problemas (para las técnicas conocidas actualmente) 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 por el método de factorización de Fermat ), incluso los algoritmos de factorización prima más rápidos en las computadoras más rápidas pueden tardar suficiente tiempo para hacer que la búsqueda sea impráctica; es decir, a medida que aumenta el número de dígitos del entero que se está factorizando, aumenta drásticamente el número de operaciones necesarias para realizar la factorización en cualquier computadora.
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 factorizara de manera eficiente un número entero arbitrario haría que la criptografía de clave pública basada en RSA fuera insegura.
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 comprobación de si un número entero es primo se puede realizar en tiempo polinómico , por ejemplo, mediante la prueba de primalidad AKS . Sin embargo, si se trata de números compuestos, las pruebas en tiempo polinómico no ofrecen ninguna información sobre cómo obtener los factores.
Dado un algoritmo general para la factorización de números enteros, cualquier número entero puede factorizarse en sus factores primos constituyentes mediante la aplicación repetida de este algoritmo. La situación es más complicada con 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 primos muy grandes, la división de prueba producirá rápidamente los factores 3 y 19, pero se necesitarán 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 que inmediatamente produce b = √ a 2 − n = √ 4 = 2 y, por lo tanto, 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 tardará mucho más en factorizar el número compuesto porque el valor inicial de ⌈ √ 18848997157 ⌉ = 137292 para a es un factor de 10 de 1372933 .
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 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-núcleo de potencia de cálculo. [2] Los investigadores estimaron que un módulo RSA de 1024 bits tardaría aproximadamente 500 veces más. [3]
El mayor número semiprimo de este tipo factorizado hasta ahora fue el 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.
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 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. [4] [5]
Existen algoritmos publicados que son más rápidos que O((1 + ε ) b ) para todos los ε positivos , es decir, subexponenciales . A partir de 2022 [actualizar], 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 b bits en el tiempo:
Para las computadoras actuales, GNFS es el mejor algoritmo publicado para n grandes (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. El algoritmo de Shor solo requiere O( b 3 ) tiempo y O( b ) espacio en entradas numéricas de b bits. En 2001, el algoritmo de Shor se implementó por primera vez, utilizando técnicas de RMN en moléculas que proporcionan siete qubits. [7]
Para hablar de clases de complejidad como P, NP y co-NP, el problema debe plantearse como un problema de decisión .
Problema de decisión (factorización de enteros) : Para cada número natural y , ¿ 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 "no" se pueden verificar en tiempo polinomial. Una respuesta de "sí" se puede certificar mostrando una factorización n = d ( norte/d ) con d ≤ k . Una respuesta de "no" puede certificarse exhibiendo la factorización de n en primos distintos, 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á aceptada, 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, [9] y co-NP-completo . Por lo tanto, es un candidato para la clase de complejidad NP-intermedia .
En cambio, 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 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 extremadamente pequeña. La facilidad de la prueba de primalidad es una parte crucial del algoritmo RSA , ya que es necesario encontrar números primos grandes para comenzar.
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 entero de forma desconocida, estos métodos suelen aplicarse antes que los métodos de propósito general para eliminar factores pequeños. [10] Por ejemplo, la división por tanteo ingenua es un algoritmo de Categoría 1.
Un algoritmo de factorización de propósito general, también conocido como algoritmo de categoría 2 , de segunda categoría o de la familia Kraitchik , [10] tiene un tiempo de ejecución que depende únicamente del tamaño del entero que se va a factorizar. Este es el tipo de algoritmo que se utiliza 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 .
En teoría de números, hay muchos algoritmos de factorización de números enteros que heurísticamente tienen un tiempo de ejecución esperado.
en notación L y little-o . Algunos ejemplos de estos algoritmos son el método de la curva elíptica y la criba cuadrática . Otro algoritmo de este tipo es el método de relaciones de grupos de clases propuesto por Schnorr, [11] Seysen, [12] y Lenstra, [13] que demostraron solo asumiendo la hipótesis de Riemann generalizada no demostrada .
Lenstra y Pomerance [14] han demostrado rigurosamente que el algoritmo probabilístico Schnorr–Seysen–Lenstra tiene un tiempo de ejecución esperado L n [ 1/2 , 1+ o (1)] reemplazando el supuesto GRH con el uso de multiplicadores. El algoritmo utiliza el grupo de clases de formas cuadráticas binarias positivasdel discriminante Δ denotado por G Δ . G Δ es el conjunto de ternas de números enteros ( a , b , c ) en los que esos números enteros son primos relativos.
Dado un entero n que será factorizado, donde n es un entero positivo impar mayor que una cierta constante. En este algoritmo de factorización, el discriminante Δ se elige como un múltiplo de n , Δ = − dn , donde d es algún multiplicador positivo. El algoritmo espera que para un 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 suave.
Denotemos por P Δ el conjunto de todos los primos q con símbolo de Kronecker ( Δ/q ) = 1. Al construir un conjunto degeneradoresde G Δ y formas primas f q de G Δ conqen P Δ se produceuna secuencia de relaciones entre el conjunto de generadores y f q . El tamaño de qpuede 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 una denominada forma ambigua de G Δ , que es un elemento de G Δ de orden divisorio de 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.
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 suma de Jacobi .
El algoritmo tal como se indica 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]
![{\displaystyle L_{n}\left[{\tfrac {1}{2}},1+o(1)\right]=e^{(1+o(1)){\sqrt {(\log n)(\log \log n)}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/518dd095a6d940c8fa4c133fb2dfd510e9004f1c)
