Pollard's rho heuristic
Pollard's rho heuristic is a method used to find a number's factors. This is faster than the classic brute-force, try every number until sqrt(n) method, but it's results are highly unpredictable.
This just prints the factors.
This just prints the factors.
1 2 import sys 3 import random 4 5 def Euclid(a, b): 6 while b != 0: 7 r = a % b 8 a = b 9 b = r 10 return a 11 12 def PollardRho(n): 13 i = 1 14 x = random.randint(0, n - 1) 15 y = x 16 k = 2 17 tried = set() 18 tried.add(x) 19 while True: 20 i = i + 1 21 x = (x ** 2 - 1) % n 22 if x in tried: 23 return 24 tried.add(x) 25 d = Euclid(y - x, n) 26 if d != 1 and d != n: 27 print d # d is a factor. Print it. 28 if i == k: 29 y = x 30 k = 2 * k 31 32 def main(argv): 33 PollardRho(int(argv[0])) 34 35 if __name__ == "__main__": 36 main(sys.argv[1:])
