fork(4) download
  1. # pollard's rho algorithm for discrete logarithms
  2.  
  3. def inverse(x, m):
  4. a, b, u = 0, m, 1
  5. while x > 0:
  6. x, a, b, u = b % x, u, x, a - b // x * u
  7. if b == 1: return a % m
  8. return 0 # must be coprime
  9.  
  10. def dlog(g,t,p):
  11. # l such that g**l == t (mod p), with p prime
  12. # algorithm due to Crandall/Pomerance "Prime Numbers" sec 5.2.2
  13. from fractions import gcd
  14. def f(xab):
  15. x, a, b = xab[0], xab[1], xab[2]
  16. if x < p/3:
  17. return [(t*x)%p, (a+1)%(p-1), b]
  18. if 2*p/3 < x:
  19. return [(g*x)%p, a, (b+1)%(p-1)]
  20. return [(x*x)%p, (2*a)%(p-1), (2*b)%(p-1)]
  21. i, j, k = 1, [1,0,0], f([1,0,0])
  22. while j[0] <> k[0]:
  23. print i, j, k
  24. i, j, k = i+1, f(j), f(f(k))
  25. print i, j, k
  26. d = gcd(j[1] - k[1], p - 1)
  27. if d == 1: return ((k[2]-j[2])%(p-1) * inverse((j[1]-k[1])%(p-1),p-1)) % (p-1)
  28. m, l = 0, ((k[2]-j[2])%((p-1)/d) * inverse((j[1]-k[1])%((p-1)/d),(p-1)/d)) % ((p-1)/d)
  29. while m <= d:
  30. print m, l
  31. if pow(g,l,p) == t: return l
  32. m, l = m+1, (l+((p-1)/d))%(p-1)
  33. return False
  34.  
  35. print "dlog(83,555,997) => 129"
  36. print dlog(83,555,997) # 129
  37. print
  38. print "dlog(83,566,997) => 147"
  39. print dlog(83,566,997) # 147
Success #stdin #stdout 0.02s 9936KB
stdin
Standard input is empty
stdout
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