# pollard's rho algorithm for discrete logarithms 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 from fractions import gcd 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 print "dlog(83,555,997) => 129" print dlog(83,555,997) # 129 print "dlog(83,566,997) => 147" print dlog(83,566,997) # 147
Standard input is empty
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) => 147 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