title: Implementing Pollard's Rho Algorithm for Discrete Logarithms
body: <p>I am trying to implement Pollard's rho algorithm for computing discrete logarithms based on the description in the book <a href="http://thales.doa.fmph.uniba.sk/macaj/skola/teoriapoli/primes.pdf" rel="nofollow"><em>Prime Numbers: A Computational Perspective</em></a> by Richard Crandall and Carl Pomerance, section 5.2.2, page 232. Here is my Python code:</p>
  
  <pre><code>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 inverse(x, p): return pow(x, p-2, p)
      def f(xab):
          x, a, b = xab[0], xab[1], xab[2]
          if x &lt; p/3:
              return [(t*x)%p, (a+1)%(p-1), b]
          if 2*p/3 &lt; 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] &lt;&gt; 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]) * inverse(j[1]-k[1],p-1)) % (p-1)
      m, l = 0, ((k[2]-j[2]) * inverse(j[1]-k[1],(p-1)/d)) % ((p-1)/d)
      while m &lt;= d:
          print m, l
          if pow(g,l,p) == t: return l
          m, l = m+1, (l+((p-1)/d))%(p-1)
      return False
  </code></pre>
  
  <p>The code includes debugging output to show what is happening. You can run the code at <a href="http://ideone.com/8lzzOfX" rel="nofollow"><a href="http://ideone.com/8lzzOf" rel="nofollow">http://ideone.com/8lzzOf</a></a>, where you will also see two test cases. The first test case, which follows the <em>d</em> > 1 path, calculates the correct value. The second test case, which follows the <em>d</em> == 1 path, fails.</p>
  
  <p>Please help me find my error.</p>