Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

Computing discrete logarithms in an interval


Authors: Steven D. Galbraith, John M. Pollard and Raminder S. Ruprai
Journal: Math. Comp. 82 (2013), 1181-1195
MSC (2010): Primary 11Y16, 68W20, 11T71
Published electronically: August 17, 2012
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The discrete logarithm problem in an interval of size $ N$ in a group $ G$ is: Given $ g, h \in G$ and an integer $ N$ to find an integer $ 0 \le n \le N$, if it exists, such that $ h = g^n$. Previously the best low-storage algorithm to solve this problem was the van Oorschot and Wiener version of the Pollard kangaroo method. The heuristic average case running time of this method is $ (2 + o(1)) \sqrt {N}$ group operations.

We present two new low-storage algorithms for the discrete logarithm problem in an interval of size $ N$. The first algorithm is based on the Pollard kangaroo method, but uses 4 kangaroos instead of the usual two. We explain why this algorithm has heuristic average case expected running time of $ (1.715 + o(1)) \sqrt {N}$ group operations. The second algorithm is based on the Gaudry-Schost algorithm and the ideas of our first algorithm. We explain why this algorithm has heuristic average case expected running time of $ (1.661 + o(1)) \sqrt {N}$ group operations. We give experimental results that show that the methods do work close to that predicted by the theoretical analysis.


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


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y16, 68W20, 11T71

Retrieve articles in all journals with MSC (2010): 11Y16, 68W20, 11T71


Additional Information

Steven D. Galbraith
Affiliation: Mathematics Department, The University of Auckland, Private Bag 92019, Auckland 1142, New Zealand
Email: S.Galbraith@math.auckland.ac.nz

John M. Pollard
Affiliation: Tidmarsh Cottage, Manor Farm Lane, Tidmarsh, Reading, Berkshire RG8 8EX, United Kingdom
Email: jmptidcott@googlemail.com

Raminder S. Ruprai
Affiliation: Mathematics Department, Royal Holloway University of London, Egham, Surrey TW20 0EX, United Kingdom
Email: raminder@email.com

DOI: http://dx.doi.org/10.1090/S0025-5718-2012-02641-X
PII: S 0025-5718(2012)02641-X
Keywords: Discrete logarithm problem (DLP), random walks
Received by editor(s): December 1, 2010
Received by editor(s) in revised form: October 9, 2011
Published electronically: August 17, 2012
Additional Notes: This work was supported by EPSRC grant EP/D069904/1
Article copyright: © Copyright 2012 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.