Factorizacion

Factorización

En matemáticas, la factorización (o factoreo) es una técnica que consiste la descomposición de una expresión matemática (que puede ser un número, una suma, una matriz, un polinomio, etc) en forma de multiplicación. Existen diferentes métodos de factorización, dependiendo de los objetos matemáticos estudiados; el objetivo es simplificar una expresión o reescribirla en términos de «bloques fundamentales», que reciben el nombre de factores, como por ejemplo un número en números primos, o un polinomio en polinomios irreducibles.

El teorema fundamental de la aritmética cubre la factorización de números enteros, y para la factorización de polinomios, el teorema fundamental del álgebra. La factorización de números enteros muy grandes en producto de factores primos requiere de algoritmos sofisticados, el nivel de complejidad de tales algoritmos está a la base de la fiabilidad de algunos sistemas de criptografía asimétrica como el RSA.

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.

Factorización de enteros en tiempo polinómico

El problema de factorizar enteros en tiempo polinómico no ha sido aún resuelto. Si alguien lo consiguiera, esto tendría gran interés en el ámbito de la criptografía, ya que muchos criptosistemas dependen de su imposibilidad. En medios académicos, la existencia de tal avance sería una gran noticia; en otros círculos, sería un gran secreto, por razones obvias.

Aplicaciones prácticas

La dureza de este problema, se encuentra en el núcleo de varios sistemas criptográficos importantes. Un algoritmo veloz para la factorización de enteros significaría que el algoritmo de clave pública RSA es inseguro. Cualquier método que logre quebrarlos puede ser utilizado para crear un algoritmo de factorización más veloz; si la factorización de enteros es veloz, éstos se vuelven más duros. En contraste, pueden existir ataques más eficientes al problema RSA, pero no se conoce ninguno.

Un problema duro similar con aplicaciones criptográficas es el problema del logaritmo discreto.

...