On the Efficiency of Pollard's Rho Method for Discrete Logarithms
231. Shi Bai and R. P. Brent,
On the efficiency of Pollard's rho method for discrete logarithms,
The Australasian Theory Symposium (CATS2008),
Wollongong, Jan. 2008;
Conferences in Research and
Practice in Information Technology, Vol. 77,
edited by James Harland and Prabhu Manyem,
Australian Computer Society, 2008, 125-131.
Paper:
pdf (248K).
Abstract
Pollard's rho method is a randomized algorithm for computing discrete
logarithms. It works by defining a pseudo-random sequence and then detecting
a match in the sequence. Many improvements have been proposed, while few
evaluation results and efficiency suggestions have been reported. This paper
is devoted to a detailed study of the efficiency issues in Pollard's rho
method. We describe an empirical performance analysis of several widely
applied algorithms and suggest a better setup of parameters. This should
provide a better combination of algorithms and a good choice of parameters
for Pollard's rho method.
Postscript
John Pollard has pointed out to us that the collision detection algorithm
used in the paper could be speeded up by using the idea of distinguished
points introduced in the paper by P.C van Oorschot and M.J.Wiener,
"Parallel collision search with cryptanalytic applications", Journal of
Cryptology 12 (1999), 1-28. Although introduced in order to give
parallel versions of the rho and kangaroo methods for discrete logs, the
idea also applies to the serial versions of both.
Go to next publication
Return to Richard Brent's index page