Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

On random walks for Pollard’s rho method
HTML articles powered by AMS MathViewer

by Edlyn Teske PDF
Math. Comp. 70 (2001), 809-825 Request permission

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
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
  • Email: eteske@cacr.math.uwaterloo.ca
  • Received by editor(s): February 23, 1999
  • Received by editor(s) in revised form: May 24, 1999
  • Published electronically: February 18, 2000
  • © Copyright 2000 American Mathematical Society
  • Journal: Math. Comp. 70 (2001), 809-825
  • MSC (2000): Primary 11Y16; Secondary 65C05, 94A60
  • DOI: https://doi.org/10.1090/S0025-5718-00-01213-8
  • MathSciNet review: 1697652