|
sys.exit()
</syntaxhighlight>
=== Java code sample===
<syntaxhighlight lang="java">
import java.math.BigInteger;
//Using package java.math so that its not limited to overflows issues like
//c/c++ example above
public class Pollard_Methods {
public BigInteger Pollards_rho_algorithm(BigInteger num)
{
BigInteger x = BigInteger.TWO ;
BigInteger y = BigInteger.TWO ;
BigInteger factor = BigInteger.ONE ;
BigInteger difference ;
while( factor.compareTo(BigInteger.ONE) == 0 )
{
x=G(x,num) ;
y=G(G(y,num),num) ;
difference = x.subtract(y) ;
difference = difference.abs();
factor = difference.gcd(num) ;
}
if( factor.compareTo(num) == 0 ) //if algorithm failed
return BigInteger.ONE ;
return factor; // if succeeded find factor
}
//computes the function (a^2+1) mod m
private BigInteger G( BigInteger a , BigInteger m)
{
a=a.pow(2) ;
a=a.add(BigInteger.ONE) ;
a=a.mod(m) ;
return a;
}
public static void main(String[] args) {
/*
For F8 aka Fermat 8th number which as stated above took 2 hours on a UNIVAC computer
Now can be done with this code in a couple minutes with no special optimization
How far we have come!!!
Just comment it in to see for yourself
String n = "115792089237316195423570985008687907853269984665640564039457584007913129639937" ;
*/
String n = "10403" ; //test factoring 10403
BigInteger num = new BigInteger(n) ;
Pollard_Methods pollM = new Pollard_Methods() ;
BigInteger resultfactor = pollM.Pollards_rho_algorithm(num) ;
System.out.println("factor = " + resultfactor.toString()) ;
}
}
</syntaxhighlight>
<br>
=== The results ===
The first repetition modulo 101 is 97 which occurs in step 17. The repetition is not detected until step 23, when <math>x \equiv x_{fixed} \pmod{101}</math>. This causes <math>\gcd (x - x_{fixed}, n) = \gcd (2799 - 9970, n)</math> to be <math>p = 101</math>, and a factor is found.
== Complexity ==
| 