On the efficiency of Pollard's Rho method for discrete logarithms

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. This should provide a better combination of algorithms and a good choice of parameters for Pollard's rho method.