Factorización de números enteros

En matemáticas, la factorización de números enteros, también conocida como factorización prima, es el proceso de escribir un número entero positivo en el producto de varios divisores. Por ejemplo, dado el número 45, se puede factorizar en 9 × 5. Según el Teorema Fundamental de la Aritmética, dicha factorización debería ser única. Esta pregunta tiene implicaciones importantes en los campos del álgebra, la criptografía, la teoría de la complejidad computacional y las computadoras cuánticas. Introducción básica Nombre chino: factorización de enteros Nombre extranjero: factorización de enteros Alias: factorización primaria Definición: un entero positivo se escribe como el producto de varios números aproximados Teorema relacionado: Teorema fundamental de la aritmética Campos aplicables: álgebra, factorización de criptografía, aplicaciones prácticas, desarrollos actuales , dificultad y complejidad, algoritmos de factorización de enteros, algoritmos de propósito especial, algoritmos de propósito general, otros algoritmos, algoritmos de factorización de enteros, algoritmos de propósito especial, algoritmos de propósito general, otros algoritmos algoritmos, otros algoritmos, factores La lista completa de factores se puede derivar de la factorización aproximada comenzando desde cero y aumentando las potencias hasta igualar este número. Por ejemplo, dado que 45 = 3 2 × 5, 45 se puede reemplazar por 3 0 × 5 0, 3 0 × 5 1, 3 1 × 5 0, 3 1 × 5 1, 3 2 × 5 0 y 3 2 × 5 1 o 1, 5, 3, 9, 15 y 45 son divisibles. La factorización aproximada, por otro lado, sólo incluye factores aproximados. Aplicación práctica Dados dos números aproximados, es fácil multiplicarlos. Sin embargo, no es tan fácil encontrar sus factores dados sus productos. Ésta es la clave de muchos criptosistemas modernos. Si se pudiera encontrar una manera rápida de resolver el problema de factorización de enteros, se podrían romper varios criptosistemas importantes, incluido el algoritmo de clave pública RSA y el generador de números aleatorios Blum Blum Shub. Aunque la descomposición rápida es una forma de piratear estos sistemas, habrá otros métodos que no impliquen descomposición. Por lo tanto, si bien el problema de la factorización de números enteros sigue siendo muy difícil, es muy posible que estos criptosistemas se rompan muy rápidamente. Algunos criptosistemas ofrecen garantías aún más sólidas: si se pueden romper rápidamente (es decir, dentro de la complejidad del tiempo polinómico), los algoritmos utilizados para romperlos también se pueden usar para factorizar números enteros rápidamente (dentro de la complejidad del tiempo polinómico). En otras palabras, romper este tipo de criptosistema no es más fácil que la factorización de números enteros. Dichos criptosistemas incluyen el criptosistema Rabin (una variante de RSA) y el generador de números aleatorios Blum Blum Shub. Novedades de hoy En 2005, como parte de un estudio público, se descompuso RSA-200 (de hasta 663 bits binarios de longitud) utilizando un método común. Si un gran número de n dígitos binarios es el producto de dos números aproximados de tamaño casi igual, no existe ningún buen algoritmo que pueda factorizarlo en tiempo polinómico. Es decir, actualmente no existe ningún algoritmo conocido que pueda descomponerlo en tiempo O(n) (k es una constante). Pero los algoritmos existentes también son más rápidos que Θ(e). En otras palabras, los mejores algoritmos que conocemos ahora son más rápidos que el tiempo exponencial y más lentos que el tiempo polinómico. El tiempo de ejecución asintótico más famoso es el filtro de campo numérico general (GNFS). Su momento es Para una computadora normal, GNFS es el mejor método que conocemos para procesar aproximadamente n dígitos binarios. Sin embargo, con los ordenadores cuánticos, Peter Showers descubrió en 1994 un algoritmo que podía resolver este problema en tiempo polinomial. Si se construyen ordenadores cuánticos a gran escala, esto será muy importante para la criptografía. Este algoritmo solo requiere tiempo O (n) y espacio O (n). En 2001, la primera computadora cuántica de 7 qubits fue la primera en ejecutar este algoritmo y descomponer 15 números. Dificultad y complejidad No está claro a qué nivel de complejidad cae la descomposición de enteros. Sabemos que la forma de problema de decisión de este problema ("Preguntar si N es una aproximación menor que M?") es tanto NP como NP inverso.

Esto se debe a que, ya sea que la respuesta sea sí o no, podemos verificar la respuesta mediante la factorización prima y la prueba de factores primos. Según el algoritmo de Sauer, este problema pertenece a BQP. Por otro lado, la mayoría de la gente sospecha que el problema no entra en las tres categorías de complejidad: P, NP-completo y anti-NP-completo. Si se puede demostrar que el problema es NP-completo o anti-NP-completo, entonces podemos deducir que NP = anti-NP, lo que será un resultado impactante, por lo que la mayoría de la gente sospecha que el problema de factorización de enteros no pertenece a la categoría de grado complejo anterior. Curiosamente, determinar si un número entero es primo es mucho más sencillo que factorizarlo, y el algoritmo AKS demuestra que el primero se puede resolver en tiempo polinomial. Probar si un número es primo es una parte muy importante del algoritmo RSA porque comienza encontrando números primos muy grandes. Algoritmos de factorización de enteros Algoritmos de propósito especial El tiempo de ejecución de un algoritmo de factorización particular depende de sus propios factores desconocidos: tamaño, tipo, etc. El tiempo de ejecución de diferentes algoritmos también varía. División de prueba de factorización de halcón Algoritmo RHO de Pollard Algoritmo de factorización de agrupación algebraica, incluido el algoritmo p ?1 de Pollard, el algoritmo p 1 de Williams y la factorización de curva elíptica de Lenstra Determinación de los números primos de Fermat Factorización de campos numéricos especiales de Euler Filtrado de algoritmos generales El tiempo de ejecución de un general El algoritmo depende sólo de la longitud del número entero defactorizado. Este algoritmo se puede utilizar para factorizar números RSA. Los algoritmos más comunes se basan en el método de congruencia de cuadrados. Algoritmo de Dixon Factorización de fracciones de empresa (CFRAC) Filtro cuadrático Filtro racional Filtro de campo numérico general Factorización de formas cuadradas de Shanks (SQUFOF) Otros algoritmos Algoritmo de Showers.