factorización de enteros
En teoría de números , la factorización de números 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 demostrado que no exista un algoritmo eficiente. La supuesta dificultad de este problema está en el corazón de algoritmos ampliamente utilizados en criptografía como 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 de potencia informática. [1] Los investigadores estimaron que un módulo RSA de 1024 bits tardaría unas 500 veces más. [2]
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 los algoritmos de factorización prima más rápidos en el las computadoras más rápidas pueden tardar lo suficiente como para que la búsqueda no sea práctica; es decir, a medida que aumenta la cantidad de dígitos de los 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 .
Por 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.
