Pollard's Rho Heuristic in Python

This a homegrown function with some problems. My guess is that I've fudged somewhere in the loop. It doesn't give consistent answers - I get that that's what "heuristic" means, but I think this should no problem for, say, n==57.

def Rho_Heuristic(n):
    import random
    cum_d = 1
    x = random.randint(0, n-1)
    y = x
    k = 2
    i = 1
    while not(cum_d == n):
      i = i + 1
        x = (x*x-1)%n
        d = GCD(y-x, n)
       if (not(d == 1) and not(d == n)):
           print d
           cum_d = 开发者_StackOverflow中文版(d * cum_d)
       if i==k:
           y = x
           k = 2*k;

---

Pollard's Rhos heuristic is an heuristic. The returned factors will always be correct, it will just rarely return all of them. PRH is good if you need to find factors with a certain characteristics. When I implemented a proof of concept RSA Attack, I just kept running it until I got primes that made sense.

---

If you want deterministic output for any given inputs, call :

random.seed(0) 

When you start your program.