## 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, xab, xab
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 <> k:
print i, j, k
i, j, k = i+1, f(j), f(f(k))
print i, j, k
d = gcd(j - k, p - 1)
if d == 1: return ((k-j)%(p-1) * inverse((j-k)%(p-1),p-1)) % (p-1)
m, l = 0, ((k-j)%((p-1)/d) * inverse((j-k)%((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