Content deleted Content added
Undid revision 1031614368 by Charmoniumq (talk) per WP:SEEALSO: already prominently linked in main article text |
→Java Code: Add java code for Pollards rho method Tags: Reverted Visual edit |
||
Line 118:
sys.exit()
</syntaxhighlight>
=== Java Code ===
<pre>
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) {
String n = "8051" ; //test factoring 8051
BigInteger num = new BigInteger(n) ;
Pollard_Methods pollM = new Pollard_Methods() ;
BigInteger resultfactor = pollM.Pollards_rho_algorithm(num) ;
System.out.println("factor = " + resultfactor.toString()) ;
}
}
</pre>
<br>
=== The results ===
Line 175 ⟶ 237:
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 ==
| |||