Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



On random walks for Pollard’s rho method

Author: Edlyn Teske
Journal: Math. Comp. 70 (2001), 809-825
MSC (2000): Primary 11Y16; Secondary 65C05, 94A60
Published electronically: February 18, 2000
MathSciNet review: 1697652
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We consider Pollard’s rho method for discrete logarithm computation. Usually, in the analysis of its running time the assumption is made that a random walk in the underlying group is simulated. We show that this assumption does not hold for the walk originally suggested by Pollard: its performance is worse than in the random case. We study alternative walks that can be efficiently applied to compute discrete logarithms. We introduce a class of walks that lead to the same performance as expected in the random case. We show that this holds for arbitrarily large prime group orders, thus making Pollard’s rho method for prime group orders about $20\%$ faster than before.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y16, 65C05, 94A60

Retrieve articles in all journals with MSC (2000): 11Y16, 65C05, 94A60

Additional Information

Edlyn Teske
Affiliation: University of Waterloo, Department of Combinatorics and Optimization, Waterloo, Ontario, Canada N2L 3G1

Keywords: Pollard’s rho method, discrete logarithm, random walks in groups
Received by editor(s): February 23, 1999
Received by editor(s) in revised form: May 24, 1999
Published electronically: February 18, 2000
Article copyright: © Copyright 2000 American Mathematical Society