## [Factorización Entera](/es/node/62909) Definición El proceso de descomponer un entero compuesto en un producto de enteros más pequeños, habitualmente en factores primos; para n>1 significa producir un multiconjunto {p_i} de primos con n=∏ p_i^{e_i}. ## Principio Principio La factorización de enteros aprovecha la estructura aritmética (divisibilidad, orden de elementos módulo n, factorizaciones algebraicas) y técnicas algorítmicas (división por prueba, cribas, Pollard rho, métodos de curvas elípticas, criba del cuerpo de números) para recuperar factores no triviales; su dureza sustenta muchas suposiciones criptográficas. ## Demostración Demostración Algoritmos concretos: la división por prueba encuentra rápidamente factores primos pequeños; Pollard rho halla factores moderados mediante paseos pseudoaleatorios; ECM es eficaz para factores primos de tamaño medio; el criba general de cuerpos de números (GNFS) es el método asintóticamente más rápido conocido para enteros grandes y se usa en factorizaciones récord. ## Aplicación incorrecta Aplicación incorrecta Suponer que una heurística única o un algoritmo con parámetros pequeños factorizará eficientemente todos los enteros (por ejemplo esperar que Pollard rho tenga éxito en semiprimos con factores muy grandes), o confundir la factorización de enteros con la factorización de polinomios o con la prueba de primalidad. ## Consecuencia Consecuencia La factorización exitosa proporciona la información aritmética completa sobre n (su descomposición en primos) y rompe esquemas criptográficos basados en la supuesta dificultad de factorizar; los avances algorítmicos cambian el umbral de seguridad práctica e influyen en recomendaciones de tamaño de claves. ## Inversión Inversión La inversión es la prueba de primalidad: en lugar de producir factores, se decide si n es primo; una decisión afirmativa de primalidad hace innecesaria la factorización, mientras que la factorización aporta información estrictamente más fuerte y generalmente más difícil de obtener. ## Límite Límite La tarea se aplica a enteros presentados en representación estándar; excluye factorizar ideales en cuerpos numéricos, factorizar polinomios sobre campos (algoritmos y complejidad distintos) y problemas en los que la forma especial de un entero o una estructura auxiliar puede explotarse por separado. ## Tensión semántica Tensión semántica Tensión entre la complejidad teórica en el peor caso y la dureza 'típica' práctica: algunos enteros (formas especiales) se factorizan fácilmente mientras que semiprimos aleatorios grandes resisten todos los algoritmos conocidos; también hay confusión entre factorizar un entero y calcular estructura multiplicativa en otros objetos algebraicos. ## Síntesis Síntesis La factorización entera es la tarea computacional de descomponer un entero en sus primos constituyentes mediante un espectro de algoritmos que explotan la divisibilidad y la estructura algebraica; su dificultad práctica depende del tamaño y la forma especial de los factores y posee implicaciones centrales para la teoría de números computacional y la criptografía.