Marathoncode: Algoritmo Pollard's rho

domingo, 26 de agosto de 2012

Algoritmo Pollard's rho

O Algoritmo $\rho$ de Pollard é um algoritmo de fatorização desenvolvido por Pollard em 1975. O algoritmo $\rho$ Pollard é baseado em dois aspectos importantes.

1) O algoritmo utiliza uma função módulo n como um gerador de sequência pseudo-aleatória.

$x_{n+1} = {x_{n}}^2 + a$ (mod n)

A sequência gera números pseudo-aleatórios distintos até cair em um ciclo. O tempo esperado até a sequência tornar-se cíclica e o tamanho esperado do ciclo são proporcionais a $\sqrt{n}$. A mesma observação realizada no paradoxo do aniversário garante esse fato

Podemos descobrir se dois números x e y, são congruentes módulo p, realizamos o seguinte cálculo

$MDC( abs(x-y), n) \leq n$

que é igual a p.

2) A detecção do ciclo na sequência é baseada na idéia atribuída a
Floyd conhecida como algoritmo da tartaruga e do coelho comparando a sequência $x_{i}$ com $x_{2i}$ para todo i. A sequência $x_{i}$ representa a tartaruga e a sequência $x_{2i}$ representa o coelho que move duas vezes mais rápido.

Algoritmo

Entrada: n, the integer to be factored; and f(x), a pseudo-random function modulo n

Saída: a non-trivial factor of n, or failure.

x ← 2, y ← 2; d ← 1
While d = 1:
1. x ← f(x)
2. y ← f(f(y))
3. d ← GCD(|x − y|, n)
If d = n, return failure.
Else, return d.

Fonte: http://en.wikipedia.org/wiki/Cycle_detection

No caso do algoritmo não encontrar um fator, nós vamos utilizar um f(x) diferente. O algoritmo não funciona
quando n é primo, uma vez que, d sempre será 1.

int mulmod(int x, int y, int n){
 return ( x%n * y%n )%n;
}

int addmod(int x, int y, int n){
 return ( x%n + y%n )%n;
}

//f(x) mod n  = x*x + c mod n
int f(int x, int c, int n){
 return addmod( mulmod(x,x, n) , c , n );
}

int abs(int x){
 if(x<0) return -x;
 else return x;
}

int gcd(int a, int b){
 int r;
 while(b!=0){
  r = a%b;
  a = b;
  b = r;
 }
 return a;
}

int primo(int n){
 
 if(n==1) return 0;
 else if( n< 4) return 1;
 else if( n%2 ==0) return 0;
 else if( n< 9) return 1;
 else if( n%3 ==0) return 0;
 else {
  int r = sqrt(n);
  int f = 5;
  
  while( f<=r){
   if(n%f==0) return 0;
   if(n%(f+2)==0) return 0;
   f=f+6;
  }
 }
 return 1;
 
}

int rho( int (*f)(int, int , int) ,int c, int n){
 int x,y,d;
 x = 2;
 y = 2;
 d = 1;
 
 if (primo(n)) return -1;
 
 while(d==1){
  x = f(x,c,n);
  y = f(f(y,c,n),c, n);
  d = gcd(abs(x-y), n);
    
 }
 
 if(d==n) return rho(f,++c, n);
 else return d;
 
}




Seja n = 8051 e f(x) = (x² + 1 ) mod 8051.

i x_i y_i GCD(|x_i − y_i|, 8051)
1 5 26 1
2 26 7474 1
3 677 871 97


Seja n = 8051 e f(x) = (x² + 2 ) mod 8051.

i x_i y_i GCD(|x_i − y_i|, 8051)
1 6 38 1
2 38 5709 1
3 1446 3607 1
3 5709 1227 83