Paper 2010/617
Computing Discrete Logarithms in an Interval
Steven D. Galbraith, John M. Pollard, and Raminder S. Ruprai
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 lowstorage 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 lowstorage 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 GaudrySchost 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. This is a revised version since the published paper that contains a corrected proof of Theorem 6 (the statement of Theorem 6 is unchanged). We thank Ravi Montenegro for pointing out the errors.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Published elsewhere. Minor revision. Math. Comp., 82, No. 282 (2013) 11811195.
 DOI
 10.1090/S00255718201202641X
 Keywords
 discrete logarithm problem (DLP)
 Contact author(s)
 S Galbraith @ math auckland ac nz
 History
 20181123: revised
 20101208: received
 See all versions
 Short URL
 https://ia.cr/2010/617
 License

CC BY
BibTeX
@misc{cryptoeprint:2010/617, author = {Steven D. Galbraith and John M. Pollard and Raminder S. Ruprai}, title = {Computing Discrete Logarithms in an Interval}, howpublished = {Cryptology ePrint Archive, Paper 2010/617}, year = {2010}, doi = {10.1090/S00255718201202641X}, note = {\url{https://eprint.iacr.org/2010/617}}, url = {https://eprint.iacr.org/2010/617} }