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

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

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

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

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

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

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 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

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.