Continuando con la serie de artículos sobre factorización, hoy veremos el método Rho de Pollard. Un instructivo algoritmo que permite factorizar números bastante más grandes que los que podríamos factorizar mediante divisiones sucesivas de números primos o aplicando directamente el método de Fermat, tal y como vimos en "Factorización I: Introducción".
A lo largo de este artículo (y de los siguientes) se usará la operación mod. Esta operación representa el resto de una división entera. Por ejemplo 6 mod 5 =1 pues si dividimos seis entre cinco la division no es exacta, dado que tiene resto 1. Otros ejemplos pueden ser: 101 mod 99 = 2, 4^2 mod 15=1 o 33² mod 989 = 10².
Ahora supongamos que tenemos la ecuación F(x)=x² mod n. Si aplicamos esta ecuación para diferentes valores de x queda claro que el resultado siempre será menor que n. Por lo tanto, si aplicamos la ecuación para diferentes valores de x es lógico pensar en que en algun momento los resultados empezarán a repetirse, pues son finitos!
Veamos un ejemplo para n=323, empezando por ejemplo con x=2.
F(2) = 2² mod 323 = 4
F(4) = 4² mod 323 = 16
F(16) = 16² mod 323 = 256
F(256) = 256² mod 323 = 290
F(290) = 290² mod 323 = 120
F(120) = 120² mod 323 = 188
F(188) = 188² mod 323 = 137
F(137) = 137² mod 323 = 35
F(35) = 35² mod 323 = 256
F(256) = 16² mod 323 = 290
F(290) = 290² mod 323 = 120
Como se ve marcado en rojo, a partir de F(35) los resultados empiezan a repetirse, entrando en un ciclo.
Si representamos en un dibujo los resultados obtenidos vemos que su forma es similar al de la letra griega rho. Lo que da nombre al algoritmo.
El algoritmo Rho de Pollard permite encontrar ciclos cuando se trabaja con grupos donde los elementos son finitos. De manera que lo único que hemos hecho hasta ahora es encontrar un ciclo en un campo de números finitos con n=323. Pero, ¿Cómo aplicar esto para factorizar?
Si nos fijamos bien en la Rho dibujada vemos un hecho interesante producido al cerrar el ciclo. Llegamos al número 256 tanto a partir de 16² como a partir de 35². Este hecho, conocido como colisión, nos permite ver que 35²=16² mod 323. Lo que se conoce como congruencia y significa que 35² mod 323 = 16². Así pues, de forma similar a como vimos en el método de Fermat encontraremos un factor p mediante 35-16=19.
Resumiendo, el algoritmo Rho de Pollard nor permitirá encontrar colisiones, que a su vez nos permitiran encontrar un factor de n.
Para aplicar el método Rho de Pollard tal y como lo hemos visto, es necesario almacenar todos los elementos y compararlos con los elementos nuevos que se van generando. Esto es muy costoso tanto en tiempo como en espacio. Afortunadamente, existe una variación conocida como método de Floyd para encontrar ciclos, que permite encontrar una colisición sin almacenar apenas datos. Este método consiste en mantener dos valores. El primero recorrera en cada paso un elemento de la Rho, el segundo recorrerá dos. El tiempo estimado en el que ambos se encontrarán de nuevo, formando una colisión, es en el peor de los casos la raiz de n.
Algoritmo:
1. Elegir un entero aleatorio a entre 1 y n-3.
2. Elegir un entero aleatorio s entre 0 y n-1.
3. Inicializar U=V=s;
4. Calcular U=F(U), V=F(F(V)));
5. Si MCD(U-V, n) = 1, volver al punto 4.
6. Si MCD(U-V, n) = n, volver al punto 1.
7. MCD(U-V, n) es un factor de n.
NOTA: MCD=Máximo Común Divisor.
Hemos visto que el tiempo estimado para factorizar un número es de raiz de n en el peor de los casos. Pero existe una manera de mejorar considerablemente el tiempo de resolución del algoritmo cuando se dispone de cierta información sobre uno de los factores de n.
Se estima que usando F(x)=x^(2k) +a mod n, el número de iteraciones necesarias para encontrar un factor de n es de c*RAIZ(p)/RAIZ(MCD(p-1,2K)-1).
Es decir, quanto más factores comunes existan entre p-1 y 2k, menor será el número de iteraciones necesario para encontrar p.
Si no sabemos que factores puede tener p-1 puede ser útil calcular el factorial de un número B y usarlo como k: k=B!. Cuanto más grande sea B menos operaciones seran necesarias para encontrar el factor. Pero tampoco se puede abusar del tamaño de B, pues para valores demasiado grandes el tiempo por iteración será muy elevado.
Veamos un ejemplo usando el programa rho_2k.cpp que pego al final:
$ g++ -lgmpxx rho_2k.cpp -o rho_2k
$ ./rho_2k [n number] [B bound]
El primer parámetro es el número que queremos factorizar, el segundo el número B que usaremos para calcular k mediante su factorial.
Intentemos factorizar el número de 32 bits: 2930992620606930277. Primero con B=1, que equivale a k=1:
$ ./rho_2k 2930992620606930277 1
factor: 1065951967
count: 19188
Hemos necesitado 19.188 operaciones. Intentemoslo ahora con B=10:
./rho_2k 2930992620606930277 10
factor: 2749647931
count: 9516
El número de iteraciones baja. Con B=100:
./rho_2k 2930992620606930277 100
factor: 2749647931
count: 50
Como podemos observar la mejora es tangible. Finalmente con B=1000:
./rho_2k 2930992620606930277 700
factor: 2749647931
count: 1
En una sola operacion!
Hemos visto que cuantos más factores coinciden entre p-1 i k mejores son los resultados. Hasta el punto de que si todos los factores de p-1 estan en k, se resuelve la factorización en una sola operación. Sin embargo B no puede incrementarse indefinicademente, pues el factorial crece muy rápido, y no tardaremos en llegar a valores que relentizarán demasiado las operaciones.
Finalmente dejo una copia del programa usado:
Referencias:
- Prime Numbers, A Computational Perspective. Crandall & Pomerance. Ed Springer.
A lo largo de este artículo (y de los siguientes) se usará la operación mod. Esta operación representa el resto de una división entera. Por ejemplo 6 mod 5 =1 pues si dividimos seis entre cinco la division no es exacta, dado que tiene resto 1. Otros ejemplos pueden ser: 101 mod 99 = 2, 4^2 mod 15=1 o 33² mod 989 = 10².
Ahora supongamos que tenemos la ecuación F(x)=x² mod n. Si aplicamos esta ecuación para diferentes valores de x queda claro que el resultado siempre será menor que n. Por lo tanto, si aplicamos la ecuación para diferentes valores de x es lógico pensar en que en algun momento los resultados empezarán a repetirse, pues son finitos!
Veamos un ejemplo para n=323, empezando por ejemplo con x=2.
F(2) = 2² mod 323 = 4
F(4) = 4² mod 323 = 16
F(16) = 16² mod 323 = 256
F(256) = 256² mod 323 = 290
F(290) = 290² mod 323 = 120
F(120) = 120² mod 323 = 188
F(188) = 188² mod 323 = 137
F(137) = 137² mod 323 = 35
F(35) = 35² mod 323 = 256
F(256) = 16² mod 323 = 290
F(290) = 290² mod 323 = 120
Como se ve marcado en rojo, a partir de F(35) los resultados empiezan a repetirse, entrando en un ciclo.
Si representamos en un dibujo los resultados obtenidos vemos que su forma es similar al de la letra griega rho. Lo que da nombre al algoritmo.
El algoritmo Rho de Pollard permite encontrar ciclos cuando se trabaja con grupos donde los elementos son finitos. De manera que lo único que hemos hecho hasta ahora es encontrar un ciclo en un campo de números finitos con n=323. Pero, ¿Cómo aplicar esto para factorizar?
Si nos fijamos bien en la Rho dibujada vemos un hecho interesante producido al cerrar el ciclo. Llegamos al número 256 tanto a partir de 16² como a partir de 35². Este hecho, conocido como colisión, nos permite ver que 35²=16² mod 323. Lo que se conoce como congruencia y significa que 35² mod 323 = 16². Así pues, de forma similar a como vimos en el método de Fermat encontraremos un factor p mediante 35-16=19.
Resumiendo, el algoritmo Rho de Pollard nor permitirá encontrar colisiones, que a su vez nos permitiran encontrar un factor de n.
Para aplicar el método Rho de Pollard tal y como lo hemos visto, es necesario almacenar todos los elementos y compararlos con los elementos nuevos que se van generando. Esto es muy costoso tanto en tiempo como en espacio. Afortunadamente, existe una variación conocida como método de Floyd para encontrar ciclos, que permite encontrar una colisición sin almacenar apenas datos. Este método consiste en mantener dos valores. El primero recorrera en cada paso un elemento de la Rho, el segundo recorrerá dos. El tiempo estimado en el que ambos se encontrarán de nuevo, formando una colisión, es en el peor de los casos la raiz de n.
Algoritmo:
1. Elegir un entero aleatorio a entre 1 y n-3.
2. Elegir un entero aleatorio s entre 0 y n-1.
3. Inicializar U=V=s;
4. Calcular U=F(U), V=F(F(V)));
5. Si MCD(U-V, n) = 1, volver al punto 4.
6. Si MCD(U-V, n) = n, volver al punto 1.
7. MCD(U-V, n) es un factor de n.
NOTA: MCD=Máximo Común Divisor.
Hemos visto que el tiempo estimado para factorizar un número es de raiz de n en el peor de los casos. Pero existe una manera de mejorar considerablemente el tiempo de resolución del algoritmo cuando se dispone de cierta información sobre uno de los factores de n.
Se estima que usando F(x)=x^(2k) +a mod n, el número de iteraciones necesarias para encontrar un factor de n es de c*RAIZ(p)/RAIZ(MCD(p-1,2K)-1).
Es decir, quanto más factores comunes existan entre p-1 y 2k, menor será el número de iteraciones necesario para encontrar p.
Si no sabemos que factores puede tener p-1 puede ser útil calcular el factorial de un número B y usarlo como k: k=B!. Cuanto más grande sea B menos operaciones seran necesarias para encontrar el factor. Pero tampoco se puede abusar del tamaño de B, pues para valores demasiado grandes el tiempo por iteración será muy elevado.
Veamos un ejemplo usando el programa rho_2k.cpp que pego al final:
$ g++ -lgmpxx rho_2k.cpp -o rho_2k
$ ./rho_2k [n number] [B bound]
El primer parámetro es el número que queremos factorizar, el segundo el número B que usaremos para calcular k mediante su factorial.
Intentemos factorizar el número de 32 bits: 2930992620606930277. Primero con B=1, que equivale a k=1:
$ ./rho_2k 2930992620606930277 1
factor: 1065951967
count: 19188
Hemos necesitado 19.188 operaciones. Intentemoslo ahora con B=10:
./rho_2k 2930992620606930277 10
factor: 2749647931
count: 9516
El número de iteraciones baja. Con B=100:
./rho_2k 2930992620606930277 100
factor: 2749647931
count: 50
Como podemos observar la mejora es tangible. Finalmente con B=1000:
./rho_2k 2930992620606930277 700
factor: 2749647931
count: 1
En una sola operacion!
Hemos visto que cuantos más factores coinciden entre p-1 i k mejores son los resultados. Hasta el punto de que si todos los factores de p-1 estan en k, se resuelve la factorización en una sola operación. Sin embargo B no puede incrementarse indefinicademente, pues el factorial crece muy rápido, y no tardaremos en llegar a valores que relentizarán demasiado las operaciones.
Finalmente dejo una copia del programa usado:
#include <gmpxx.h>
#include <iostream>
// F(x) = x^2k + a mod n
mpz_class F(mpz_class &x, mpz_class &k, mpz_class &a, mpz_class &n)
{
mpz_class res;
mpz_class pow;
pow = 2*k;
mpz_powm(res.get_mpz_t(), x.get_mpz_t(), pow.get_mpz_t(), n.get_mpz_t());
res += a;
return res;
}
int main(int argc, char *argv[])
{
using namespace std;
mpz_class n;
mpz_class U;
mpz_class V;
mpz_class s;
mpz_class g;
mpz_class k;
mpz_class a;
mpz_class count;
if (argc!=3)
{
cout << argv[0] << " [n number] [B bound]" << endl;
return 0;
}
n = argv[1];
int B = atoi(argv[2]);
count = 0;
s = 2;
U = s;
V = s;
g = 1;
mpz_fac_ui(k.get_mpz_t(), B);
a = 3;
while(g==1)
{
U = F(U, k, a, n);
V = F(V, k, a, n);
V = F(V, k, a, n);
g = U-V;
mpz_gcd(g.get_mpz_t(), g.get_mpz_t(), n.get_mpz_t());
if(g==n)
{
cout << "bad seed" << endl;
U++;
V++;
g=1;
}
count ++;
}
cout << endl << "factor: " << g << endl;
cout << "count: " << count << endl;
return 0;
}
Referencias:
- Prime Numbers, A Computational Perspective. Crandall & Pomerance. Ed Springer.
1 comentario:
Hola, muchas gracias. Necesitaba el algoritmo para un examen y ha sido la primera página que se ha preocupado no solo por el código si no por la explicación.
Publicar un comentario