Paper 2010/615
Using Equivalence Classes to Accelerate Solving the Discrete Logarithm Problem in a Short Interval
Steven D. Galbraith and Raminder S. Ruprai
Abstract
The Pollard kangaroo method solves the discrete logarithm problem (DLP) in an interval of size $N$ with heuristic average case expected running time approximately $2 \sqrt{N}$ group operations. A recent variant of the kangaroo method, requiring one or two inversions in the group, solves the problem in approximately $1.71 \sqrt{N}$ group operations. It is wellknown that the Pollard rho method can be spedup by using equivalence classes (such as orbits of points under an efficiently computed group homomorphism), but such ideas have not been used for the DLP in an interval. Indeed, it seems impossible to implement the standard kangaroo method with equivalence classes. The main result of the paper is to give an algorithm, building on work of Gaudry and Schost, to solve the DLP in an interval of size $N$ with heuristic average case expected running time of close to $1.36\sqrt{N}$ group operations for groups with fast inversion. In practice the algorithm is not quite this fast, due to problems with pseudorandom walks going outside the boundaries of the search space, and due to the overhead of handling fruitless cycles. We present some experimental results. This is the full version (with some minor corrections and updates) of the paper which was published in P. Q. Nguyen and D. Pointcheval (eds.), PKC 2010, Springer LNCS 6056 (2010) 368383.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Published elsewhere. Full version of paper from PKC 2010
 Keywords
 discrete logarithm problem (DLP)elliptic curves
 Contact author(s)
 s galbraith @ math auckland ac nz
 History
 20101208: received
 Short URL
 https://ia.cr/2010/615
 License

CC BY
BibTeX
@misc{cryptoeprint:2010/615, author = {Steven D. Galbraith and Raminder S. Ruprai}, title = {Using Equivalence Classes to Accelerate Solving the Discrete Logarithm Problem in a Short Interval}, howpublished = {Cryptology {ePrint} Archive, Paper 2010/615}, year = {2010}, url = {https://eprint.iacr.org/2010/615} }