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 .