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).


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.


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