# 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 intervalHTML articles powered by AMS MathViewer

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

## 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
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
• 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