Issue implementing Pollard's Rho for discrete logarithms

Question

I've been trying to implement Pollard's Rho recently. The original idea was to implement the code in several languages and put it up for everyone to see for educational purposes. I first took to Wikipedia and implemented the code from Pollard's rho algorithm for logarithms. I translated the code directly from C++ to Haskell and it generated the same output as C++ so I was happy. It agreed with the example in the Wikipedia page. However, when taking the output and solving $(B - b)\ \gamma \equiv (a - A)\pmod n$, I got results that were different than what the logarithm should be. If you would like to comment on this code, comment on the C++ code in the Wikipedia article please, I guess that's the most accessible version.

Unhappy with the Wikipedia article I searched further and found a gist with Python code that's based on Algorithm 3.60 in the Handbook of Applied Cryptography, linked in the gist. This version could calculate the logarithm for the example mentioned in the code (taken from the book). It yields different results to the code from the Wikipedia page. I have verified, and the Python code reads exactly like the algorithm is described in the book. However, if I feed it something like $n=6,\ Z=7,\ alpha=5,\ beta=4$ then obviously the $dlog$ of $4$ to the base of $5$ in $\mathbb{Z}_7^*$ should be $2$, because $5^2\pmod 7 \equiv 25\pmod 7 \equiv 4 \pmod 7$. But instead it breaks down with an exception, because it tries to get the inverse of $4\pmod 6$, and obviously there isn't one, because $gcd(4, 6) = 2 \neq 1$. It does that because in the last step of the algorithm, described on print page 106, it will arrive at $r = b_i - b_{2i} = 4$ and it has to compute $r^{-1}$. HAC is supposed to be a respectable book, but the code I have yields bad results, so am I doing something wrong? Is the book wrong?

I've spent a few days on this now. And yes, I've read through this stack exchange searching for Pollard's Rho. How do I fix this code? Why does the Python and C++ code break down? Is there a version of Pollard's Rho algorithm that generally just works other than for a few select cases? Is there a book that describes such an algorithm? Can someone point me to a working version?

Answer 1

First of all, Pollard Rho finds an essentially random solution $(B - b) \gamma \equiv (a - A) \pmod{N}$. This randomness implies that if $N$ has a prime factor $p$, then $B - b$ has a probability $1/p$ of having $p$ as a multiple (and hence it will fail in precisely the way you've seen).

Pollard Rho is normally used with $N$ being a large prime; the only prime factor $N$ has is, in fact, $N$, and so it has a tiny change ($1/N$) of failing. You, of course, are using it with toy parameters, and so the chance of failure is much higher.

This does being up a nontrivial point; in the group $Z_p^*$, $N = p-1$ is always even; doesn't this mean that Pollard-Rho always have a 50% probability of failing?

Well, it would, if we used it in the straight-forward manner. However, what we do is perform the operation in a prime subfield (or, at least, a subfield with no small factors); this makes the failure probability tiny.

If we do have to do the work in a group with a size that has small factors, say, $N = hq$, where $h$ is smooth, and $q$ has no small factors, then what we can do is compute $a^h$ and $b^h$, and use Pollards-Rho to compute $\gamma'$ such that $(a^h)^{\gamma'} \equiv (b^h)$; this is in the $q$-sized subgroup, and so has a high probability of success. Given $\gamma'$, it's easy to reconstruct $\gamma$, as $\gamma \equiv \gamma' \pmod q$

Answer 2

The problem is that Pollard Rho is not guaranteed to work, especially in very small examples where the order of the multiplicative group is 6.

With larger groups, the modular inverse will almost always work, because the cycle length that you find it is extremely unlikely to have a factor in common with the order.

If you do some larger examples, they will work more often, but will still fail some of the time.