IACR News item: 03 June 2012
Daniel J. Bernstein, Tanja Lange
ePrint ReportThis paper presents two reasons that Pollard\'s rho algorithm
is farther from optimality than generally believed.
First, ``higher-degree local anti-collisions\'\'
make the rho walk less random than the predictions made by the conventional Brent--Pollard heuristic.
Second, even a truly random walk is suboptimal,
because it suffers from ``global anti-collisions\'\' that can at least partially be avoided.
For example, after (1.5+o(1))\\sqrt(l) additions in a group of order l (without fast negation),
the baby-step-giant-step method has probability 0.5625+o(1)
of finding a uniform random discrete logarithm;
a truly random walk would have probability 0.6753\\ldots+o(1);
and this paper\'s new two-grumpy-giants-and-a-baby method has probability 0.71875+o(1).
Additional news items may be found on the IACR news page.