Pollard's ρ method
[Primes Home][Home]
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:
import sys; val=361187 if (len(sys.argv)>1): val=int(sys.argv[1]) 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(val)))