Pollard’s rho algorithm is used to factor composite integers. Suppose you have 8633, 89 *97 are the factors.
Here is the code:
static void Main(string[] args)
{
Int64 a = p.PollardRho(12187823);
}
public Int64 customFunct(Int64 param, Int64 mod)//Custom number generator
{
return ((param * param + 1 )% mod);
}
public Int64 PollardRho(Int64 number)
{
Int64 a = 2, b = 2, tmp;//initail starting values
while(true)
{
a = customFunct(a,number);//get first number
b = customFunct(customFunct(b,number),number);//get second double run custom func
tmp = GCD(Math.Abs(b-a), number);// if a = b mod d(divisor one of the divisors of our number) then a-b is multiple of d and number is multiple of d
if (tmp > 1)
break;
}
return tmp;
}
public Int64 GCD(Int64 x, Int64 y)//Greatest Common Divisor
{
if (x == 0)//Find it? return
return y;
if (y == 0)//Find it? return
return x;
x = x % y;// take the mod of the large val to small one if the order is wrong in the next recursive loop it will be correct
return GCD(y, x);//Parameters changed place
}
I put comments on the code and included usage.The code includes a custom function you may experiment with and a greatest common divisor calculator.
.