Pollard’s rho algorithm, along with parallelized, vectorized, and negating variants, is
the standard method to compute discrete logarithms in generic primeorder groups.
This paper presents two reasons that Pollard’s rho algorithm is farther from
optimality than generally believed. First, “higherdegree local anticollisions” make the
rho walk less random than the predictions made by the conventional BrentPollard
heuristic. Second, even a truly random walk is suboptimal, because it suffers from
“global anticollisions” that can at least partially be avoided. For example, after
$\left(\mathfrak{1}.\mathfrak{5}+o\left(\mathfrak{1}\right)\right)\sqrt{\ell}$ additions in a
group of order
$\ell $
(without fast negation), the babystepgiantstep method has probability
$\mathfrak{0}.\mathfrak{5}\mathfrak{6}\mathfrak{2}\mathfrak{5}+o\left(\mathfrak{1}\right)$ of finding
a uniform random discrete logarithm; a truly random walk would have probability
$\mathfrak{0}.\mathfrak{6}\mathfrak{7}\mathfrak{5}\mathfrak{3}\dots +o\left(\mathfrak{1}\right)$; and
this paper’s new twogrumpygiantsandababy method has probability
$\mathfrak{0}.\mathfrak{7}\mathfrak{1}\mathfrak{8}\mathfrak{7}\mathfrak{5}+o\left(\mathfrak{1}\right)$.
