## Pollard's ρ method[Back] In cryptograhy we often multiply two numbers together, and the challenge is to determine the two values which caused the result. For example the factors of 77 and 7 and 11. Normally this is done with prime numbers, and where we have to determine the two prime numbers which makes a given value. Computers generally find this a difficult problem, but there are methods arround to factorise without using brute force. One example is Pollard's ρ method. For example the factors of 361,187 are 953 and 379. |

## Examples

The following are some examples:

**The factors of 273 are 3 and 91**. Pollard**The factors of 116,393 are 239 and 487**. Pollard**The factors of 3,789,829 are 3209 and 1181**. Pollard**The factors of 7,388,399 are 3571 and 2069**. Pollard**The factors of 39,2524,199 are 919 and 427121**. Pollard

## Sample

A sample run shows that we keep iterating until the gcd() value is not unity. The value returned from the non unity gcd() value is then the first factor:

A B GCD 7 52 1 52 104112 1 2707 212732 1 104112 214627 1 86677 44835 1 212732 192645 379 First factor is 379

Code is:

def gcd(x,y): if y==0: return x else: return gcd(y,x%y) def f(x,n): return (x*x+3) %n def pollardrho(a): print "A B GCD" x=2 y=2 d=1 while d==1: x=f(x,a) y=f(f(y,a,),a) d=gcd(abs(x-y),a) print x,y,d if d>1 and a>d: return d if d==a: return -1 print "First factor is "+str(pollardrho(361187))