Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.78.

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.


Computing discrete logarithms in an interval
HTML articles powered by AMS MathViewer

by Steven D. Galbraith, John M. Pollard and Raminder S. Ruprai PDF
Math. Comp. 82 (2013), 1181-1195 Request permission


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.

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:
  • John M. Pollard
  • Affiliation: Tidmarsh Cottage, Manor Farm Lane, Tidmarsh, Reading, Berkshire RG8 8EX, United Kingdom
  • Email:
  • Raminder S. Ruprai
  • Affiliation: Mathematics Department, Royal Holloway University of London, Egham, Surrey TW20 0EX, United Kingdom
  • Email:
  • 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
  • © Copyright 2012 American Mathematical Society
    The copyright for this article reverts to public domain 28 years after publication.
  • Journal: Math. Comp. 82 (2013), 1181-1195
  • MSC (2010): Primary 11Y16, 68W20, 11T71
  • DOI:
  • MathSciNet review: 3008854