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 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 . Sin embargo, no se ha demostrado que no exista un algoritmo eficaz. La presunta dificultad de este problema está en el corazón de los algoritmos ampliamente utilizados en criptografía como RSA . Se han aplicado muchas áreas de las matemáticas y la informática para resolver el 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. [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 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 al azar 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 tomar el tiempo suficiente para hacer 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 .
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 compuestas, las pruebas de tiempo polinomial no dan una idea de cómo obtener los factores.
