Tuesday, 7 February 2017

Python Pollard's rho Algorithm

I've recently was looking for some number theoretic algorithms in Python and Go. While searching, found this  on the first position on duckduckgo and google but it's not really good. Even for example used (1200), gives wrong answer (missing factor 600).  
Applying small fix:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def pollard_rho(n):
    s = set()
    i = 0
    xi = randint(0, n-1)
    y = xi
    k = 2
    while i < 2 * n:
        i += 1
        xi = ((xi^2) - 1)%n
        d = gcd(y - xi, n)
        if d != 1 and d != n:
            s.add(d)
        if i == k:
            y = xi
            k *= 2
    return sorted(s)

Where gcd is Greater Common Divisor, 2 * n in line 7, makes it work correctly, but it's still slow.
Anybody needs more efficient factorization (and more), I would recommend this library.

No comments: