Pollard Rho Integer Factorization

Revision en2, by saru95, 2015-09-08 21:54:56

I am a newbie . I was studying this particular algorithm and I have some doubts that have arisen. Would be glad if someone could clear them .

My code goes like :

int pollardRho(int n) {
  if(n%2==0)
    return 2 ;
  srand (time(NULL)) ; 
  int x, y , g=1 , a;
  x = rand() % n + 1 ;
  y = x ;
  a = rand() % n + 1 ;
  while(g==1) {
    x = ((x*x) + a)%n ;  
    y = ((y*y) + a)%n ;
    y = ((y*y) + a)%n ;  
    g = gcd(abs(x - y), n) ;
  }
  return g ;
}

What I infer is that the use of (x*x) + a mod n is to generate another pseudo random number . But why cant we write it as :

int pollardRho(int n) {
  if(n%2==0)
    return 2 ;
  srand (time(NULL)) ; 
  int x, y , g=1 , a;
  while(g==1) {
    x = rand() % n + 1 ;
    y = rand() % n + 1 ;
    g = gcd(abs(x - y), n) ;
  }
  return g ;
}

where the rand() itself generates a new number . Basically, I want to know what is the significance of the equation being used .

Tags factorisation, integer

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English saru95 2015-09-08 21:54:56 38
en1 English saru95 2015-09-08 20:11:07 1014 Initial revision (published)