Cargando...
 

Descomposición en factores primos

Image
Cualquier número entero positivo se puede representar de forma única (salvo el orden) como el producto de una serie de factores primos. Seguramente ésto nos lo tenemos bien aprendido desde los tiempos del colegio, pero computacionalmente la cosa no es tan sencilla.

Este artículo ya lleva un tiempo escrito y publicado en éste sitio, pero hemos cambiado un poco el formato y hemos introducido una demo en línea del algoritmo propuesto.

A ésta características de los números enteros positivos se le llama el teorema fundamental de la aritmética(external link). Esta propiedad tan sencilla a simple vista trae enormes quebraderos de cabeza desde el punto de vista de la computación.

Este teorema tiene aplicaciones prácticas en muchos campos, aunque en los últimos años su mayor aplicación está en la criptografía. El motivo es muy sencillo, y vamos a intentar intuirlo en este artículo.

En el cole aprendimos un algoritmo simple para obtener la factorización de un número entero en sus factores primos.

Haciendo un breve repaso, éste algoritmo consiste simplemente en coger un número natural n, y probar a dividirlo por los números primos, empezando por el 2, luego el 3, luego el 5... cuando el resto de la división es 0, hemos obtenido un factor, hacemos que n valga ahora el cociente, y seguimos probando por el último primo en el que estábamos. Así indefinidamente hasta que n=1.

MINIDEMO:
En éste artículo vamos a intentar obtener un algoritmo similar, para factorizar números pequeños, al estilo de como se hace en esta demo.

(No es una pieza de software robusta ni construida con un diseño exigente. Es sólo una demo).

Examinando cómo lo hacemos a mano...

Por ejemplo, para factorizar el 350, hacemos n=350... y empezamos a probar a dividir por los números primos.

Probamos a dividir n por 2... 350/2=175, y resto 0... perfecto, hemos encontrado un factor: el 2. Hacemos n=175

Lo volvemos a intentar 175/2 = 87 y resto 1... oops... el 2 no vuelve a ser factor primo. Pasamos a probar con el 3.

175/3=58 y resto 1... el 3 no es factor primo. Pasamos al 5.

175/5=35 y resto 0 ... el 5 es factor primo. Tomamos nota (ya tenemos el 2 y el 5), y hacemos n=35

Volvemos a probar el 5... 35/5=7 y resto 0. Otra vez el 5 es factor primo (ya tenemos 2, 5 y 5). Hacemos n=7

Volvemos a probar el 5... 7/5=1 y resto 2. Ya no hay más cincos. Probamos con el 7.

7/7=1 y resto 0. El siete es factor primo (ya tenemos 2, 5, 5, y 7). Hacemos n=1... ya hemos terminado.

Así pues, 350 se puede expresar como 350=2 x 5 x 5 x 7.

El procedimiento es sencillo... pero... ¿Seremos capaces de encontrar un buen algoritmo que dado un número natural n nos devuelva sus factores primos?

Encontrar un algoritmo

Para encontrar un algoritmo de factorización nos encontramos con una serie de problemas.

El primero de ellos es que si te das cuenta, vamos avanzando por la lista de números primos... 2, 3, 5, 7... pero ¿Cómo se construye esta lista? La primera persona de quién se tiene constancia de que se planteó este problema parece ser el matemático Eratóstenes(external link), que nos dejó el algoritmo conocido como Criba de Eratóstenes?. Este algoritmo permite hallar los números primos menores que un número natural dado, pero el algoritmo es computacionalmente complejo.... tanto como el de la propia factorización.

Además... el algorimo exige un gran gasto de memoria, ya que si estamos descomponiendo el 350, necesitaremos una lista que ocupará unos pocos bytes, pero si estamos descomponiendo un número de 16 o 20 cifras, necesitaremos una cantidad de memoria que probablemente no nos podamos permitir.

Existe una forma de no construir la criba de Eratóstenes. Si nos damos cuenta, sólo hay un factor primo par: el 2. Todos los demás son impares. Podemos hacer que nuestro algoritmo intente dividir por el 2, y luego por todos los impares, aunque no sean primos.

El algoritmo seguirá funcionando, porque cuando intente dividir por un número compuesto, por ejemplo, el 35 (7*5), se descartará siempre porque el resto no será 0, ya que el algoritmo ya habrá dividido previamente por sus factores (el 5 y el 7).

Esto, que parece un desperdicio, es más eficiente que construir una criba de Eratóstenes.

Supongo que en este momento te estarás preguntando si existe alguna forma sencilla de saber si un entero es primo o no. La respuesta es que si esa prueba existe, nadie la ha descubierto todavía. (Si encuentras esa prueba sencilla y demuestras que funciona te harás inmensamente rico... mucha gente lo está intentando en este momento, pero no parece que haya avances revolucionarios). En el contexto de nuestro problema, mejor olvidarnos de la prueba... ninguna va a ser tan sencilla como probar a dividir a ver si el resto es 0, aunque el divisor sea compuesto.

Por otro lado... ¿Hasta dónde tenemos que llegar en la lista de divisores?. Quiero decir... si estamos intentando descomponer el 4731, sabemos que paramos cuando n=1, pero ¿Y si no llegamos a esa condición? ¿Cuándo paramos? Parece bastante obvio que el peor caso que nos podemos encontrar es que el 4731 sea primo, con lo cual, pararíamos al dividir 4731/4731=1 y resto 0. Haríamos n=1 y ya tenemos la condición de terminación... pero ¿Podemos parar antes? Afortunadamente sí.

Un matemático marroquí del siglo XIII llamado Al-Marrakushi Ibn al-Banna(external link) demostró que basta con probar con los numeros inferiores o iguales a la raíz cuadrada de n. Si llegados a ese punto, n es mayor que 1, entonces n contiene el último de los factores primos.

Vale, con este par de optimizaciones ya podemos construir un algoritmo de factorización. Iremos probando a dividir un número dado n por 2, y luego por todos los impares, hasta llegar a la raíz cuadrada de n. Cada vez que obtengamos un resto 0, hemos encontrado un factor primo, y asignaremos a n el cociente de la división para seguir probando.

Quizá se te ocurra alguna otra optimización... Bueno... mucha gente piensa en ellas. Puedes echar un vistazo a ésta página(external link) de Steve Litt. Hay muchas otras por Internet.

El caso es que no se han encontrado algoritmos lo suficientemente buenos como para considerarse "revolucionarios" dentro de este tema.

No obstante, nos vamos a quedar con estas dos optimizaciones, que son las que comunmente sirven para construir un algoritmo de factorización sencillito.

Aquí tienes un posible algoritmo que refleja lo que hemos comentado escrito en pseudocódigo y en C#.


List<long> Factorizar(long n)
{
    //almacenaremos los resultados de la
    //factorización en una lista
    List l<long> = new List<long>();
    long num1=n;
 
    //Mientras podamos dividir por 2
    //el dos es un factor
    while (num1 % 2 == 0)
    {
        l.Add(2);
        num1 = num1 / 2;
    }//while
 
    //ahora probaremos con los impares,
    //empezando por el 3
    long cuenta = 3;
    long raiz = (long)Math.Sqrt(num1);
 
    while (cuenta <= raiz && num1 > 1)
    {
        if (num1 % cuenta == 0)
        {
            l.Add(cuenta);
            num1 = num1 / cuenta;
        }
        else
        {
            cuenta = cuenta + 2;
        }
    }
    if (num1 > 1)
        l.Add(num1);
    return l;
}



Conclusión

Este algoritmo no está mal para aprender programación o para factorizar números pequeños.

No obstante, la cantidad de comprobaciones que hay que hacer crece demasiado deprisa conforme más grandes pudieran ser los factores primos del número a factorizar.

En criptografía, la aplicación con números primos más conocida quizá sea el sistema RSA(external link) de clave pública. En él, la clave para cifrar es pública y conocida por cualquiera, pero la clave para descifrar (que es distinta) se mantiene en secreto. La magia del RSA consiste en que si yo conozco tu clave pública (cualquier la puede conocer, ya que para eso se hace pública) y cifro un mensaje dirigido a tí con ella, nadie más que tú podrá descifrarlo, ya que eres el único que tiene la clave privada, a pesar de que tu clave pública sea perfectamente conocida y el algoritmo RSA de cifrado y descifrado también.

El truco (simplificando mucho muchísimo) consiste en que la clave pública contiene un número muy grande (llamemosle k) que es el producto de dos primos muy grandes, de varios cientos de cifras (llamémosles p y q, de tal manera que k=p x q). Para cifrar un mensaje basta con conocer k, pero para descifrarlo es necesario conocer p y q. Si yo encripto un mensaje para tí porque tú me has dicho tu clave k, tú lo puedes desencriptar porque conoces p y q. Si alquien intercepta el mensaje y no conoce p y q, pero conoce k (todos la conocemos porque la has hecho pública), puede llegar a descifralo factorizando k, y obteniendo p y q... pero un algorimo del estilo del que hemos descrito en este artículo tardaría varios años en obtener la factorización de un k muy grande utilizando los ordenadores más potentes que se conocen. Aun con algoritmos mucho mejores que éste (que existen), la mejora no es demasiado significativa. Para cuando obtuvieramos p y q habríamos gastado un montón de dinero, tiempo y probablemente el mensaje cifrado ya habría perdido todo el interés.

Muchos de los algoritmos de cifrado modernos se basan en esto. Si p y q son dos números primos muy grandes, la operación de obtener su producto k=p x q se puede computar en cualquier ordenador de una forma muy eficiente (en unos pocos segundos como mucho). Sin embargo, dado un k que es producto de dos números primos muy grandes, puede tardar varios años en factorizarse.

Si alguien obtuviera una forma eficiente de factorizar números muy grandes, gran parte de la criptografía moderna se iría al garete, pero de momento, parece que va a ser que no.

Ultima edición por vic .
Página última modificacion en Viernes 17 de Agosto, 2012 16:06:34 CEST.


Quizá te interese también

¿Dónde estoy?

Estás en La tecla de ESCAPE, un sitio web personal en el que nos gusta hablar de algoritmos, metodología de la programación, personajes de informática, tecnología, ingeniería del software, internet, y cualquier otra tontería que se nos ocurra.
Leer más / Términos de uso (ToS)

Este sitio web usa cookies para su funcionamiento. Navegar por éste sitio supone la aceptación de la política de cookies -
Política de cookies +