factorización de enteros

En teoría de números, la factorización de enteros, factorización de primos, factorización en primos o árbol de factorización consiste en descomponer un número compuesto (no primo) en divisores no triviales, que cuando se multiplican dan el número original. Cuando los números son muy grandes no se conoce ningún algoritmo que resuelva eficientemente este problema; un reciente intento de factorizar un número de 200 dígitos tardó 18 meses y consumió más de medio siglo de tiempo de cálculo. Su supuesta dificultad es el núcleo de ciertos algoritmos criptográficos, como el RSA. Muchas áreas de las matemáticas y de las ciencias de la computación, como la teoría algebraica de números, las curvas elípticas o la computación cuántica, están relacionadas con este problema. Descomponer dos números de igual longitud no tiene por qué tener la misma complicación. Actualmente (2006) se considera que los casos más duros son aquellos para los que los factores son dos números primos, elegidos al azar, de aproximadamente el mismo tamaño.