Factorización de enteros

En teoría de números, la factorización de enteros o factorización de primos 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 ( RSA-200) 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.

Descomposición en factores primos

La imagen demuestra la descomposición en primos del número 864. Un método rápido de escribir el resultado en números primos es .

Por el teorema fundamental de la aritmética, cada entero positivo tiene una única descomposición en números primos ( factores primos). La mayor parte de los algoritmos de factorización elementales son de propósito general, es decir, permiten descomponer cualquier número introducido, y solo se diferencian sustancialmente en el tiempo de ejecución.

Other Languages