Pollard's rho algorithm

[menopaws]

Hi!

Trying to implement Polards Algorithm:
http://en.wikipedia.org/wiki/Pollard's_rho_algorithm

Cant really get it right tho,i get my "X" values right,but not "Y"´s..


#include <iostream>
#include <math.h>
#include <ctime>
using namespace std;
long long gcd(long long a,long long b)
{
return b==0?
a:gcd(b,a%b);
}

int main()
{

	long long n=115;
	long long y=2;
	long long x=2;
	
	long long d=1;	


	//for(int i=0;i<3;i++)
	//{
	//	x=(x*x+1)%n;
	//	y=(x*x+1)%n;

	//	d=gcd(n,x-y);

	//	cout<<"==========""turn "<<i<<endl;
	//	cout<<"x: "<<x<<endl;
	//	cout<<"y: "<<y<<endl;
	//	cout<<"D: "<<d<<endl;

	//}
	while(d>1&&d<n)
	{
		x=(x*x+1)%n;
		y=(x*x+1)%n;
		d=gcd(n,x-y);		
	}
	cout<<"Divisor:"<<d<<endl;

	return 0;
}

The outcommented for loop is just me checking X and Y values.
X values seem to be right,but X´s is off. "D" should be 5,with n=115.

Hope someone can help me out,thanks in advance!

[Peter87]

If you are implementing the algorithm in the wikipeida page you are doing a few things wrong.

Line 24 should be while(d == 1)

Line 27 is probably wrong. Note that they use f(f(y)) and not f(y).

line 28 you should use the absolute value of x-y.

[menopaws]

Yeah,i know it says d==1 on the wiki page,i was using my declaration cause it worked even when d is negative(because of my gcd function).

But using absolute value should take care of that:)

	while(d==1)
	{
		x=(x*x+1)%n;
		y=(x*x+1)%n;
		d=gcd(n,abs(x)-abs(y));
	}

Still dont know tho what i should about the Y value tho..

[Peter87]

I think this is how it should be

while(d==1)
{
	x=(x*x+1)%n;
	y=((y*y+1) * (y*y+1) + 1)%n;
	gcd(n,abs(x - y));
}

It is probably more readable if you define the function f (name it whatever you want) and use that in your code.

[menopaws]

Dosent work:(


Oh well,gonna try it again later on..

[menopaws]

Actually it does,i get 23 as divisor,115/23=5.