Pollard’s Rho Algorithm For Discrete Logarithms

May 27, 2016

Here’s my solution, written in Python because it is clearer and easier to read:

from fractions import gcd

def inverse(x, m):
    a, b, u = 0, m, 1
    while x > 0:
        x, a, b, u = b % x, u, x, a - b // x * u
    if b == 1: return a % m
    return 0 # must be coprime
 
def dlog(g,t,p):
    # l such that g**l == t (mod p), with p prime
    # algorithm due to Crandall/Pomerance "Prime Numbers" sec 5.2.2
    def f(xab):
        x, a, b = xab[0], xab[1], xab[2]
        if x < p/3:
            return [(t*x)%p, (a+1)%(p-1), b]
        if 2*p/3 < x:
            return [(g*x)%p, a, (b+1)%(p-1)]
        return [(x*x)%p, (2*a)%(p-1), (2*b)%(p-1)]
    i, j, k = 1, [1,0,0], f([1,0,0])
    while j[0] <> k[0]:
        print i, j, k
        i, j, k = i+1, f(j), f(f(k))
    print i, j, k
    d = gcd(j[1] - k[1], p - 1)
    if d == 1: return ((k[2]-j[2])%(p-1) * inverse((j[1]-k[1])%(p-1),p-1)) % (p-1)
    m, l = 0, ((k[2]-j[2])%((p-1)/d) * inverse((j[1]-k[1])%((p-1)/d),(p-1)/d)) % ((p-1)/d)
    while m <= d:
        print m, l
        if pow(g,l,p) == t: return l
        m, l = m+1, (l+((p-1)/d))%(p-1)
    return False

This code has debugging output, so you can see what is happening. Here are two examples:

>>> dlog(83,555,997) # 129
1 [1, 0, 0] [555, 1, 0]
2 [555, 1, 0] [4, 2, 1]
3 [949, 2, 0] [805, 4, 1]
4 [4, 2, 1] [904, 5, 2]
5 [226, 3, 1] [64, 6, 3]
6 [805, 4, 1] [798, 14, 6]
7 [16, 4, 2] [185, 28, 14]
8 [904, 5, 2] [666, 29, 15]
9 [257, 5, 3] [837, 58, 32]
10 [64, 6, 3] [442, 58, 34]
11 [625, 7, 3] [4, 116, 69]
12 [798, 14, 6] [805, 118, 69]
13 [432, 14, 7] [904, 119, 70]
14 [185, 28, 14] [64, 120, 71]
15 [981, 29, 14] [798, 242, 142]
16 [666, 29, 15] [185, 484, 286]
17 [443, 29, 16] [666, 485, 287]
18 [837, 58, 32] [837, 970, 576]
0 46
1 129
129

>>> dlog(83,566,997) # 977
1 [1, 0, 0] [566, 1, 0]
2 [566, 1, 0] [97, 3, 0]
3 [319, 2, 0] [36, 5, 0]
4 [97, 3, 0] [666, 12, 0]
5 [67, 4, 0] [837, 24, 2]
6 [36, 5, 0] [442, 24, 4]
7 [436, 6, 0] [4, 48, 9]
8 [666, 12, 0] [279, 50, 9]
9 [443, 12, 1] [994, 102, 18]
10 [837, 24, 2] [270, 102, 20]
11 [678, 24, 3] [388, 104, 20]
12 [442, 24, 4] [748, 208, 41]
13 [949, 48, 8] [279, 209, 42]
14 [4, 48, 9] [994, 420, 84]
15 [270, 49, 9] [270, 420, 86]
977

Note that the second problem gives a different answer than the brute-force solution from a previous exercise. That’s because 83 is not a generator of the group 1, 2, …, 997, as Pollard’s algorithm requires.

You can run the program at http://ideone.com/wUORDz.

Pages: 1 2

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: