Computing discrete logarithms with the parallelized kangaroo method. (Q1408372): Difference between revisions

Some methods to solve the Discrete Logarithm Problem (DLP) take advantage of some specific property of the underlying cyclic group (the archetype being the Index-Calculus method which provides a subexponential-time algorithm to attack DLP on the multiplicative group of a finite field, group used in cryptographic applications) while others are generic (valid for any cyclic group) like the BSGS of Shanks, the rho and the kangaroo methods. The kangaroo method due to \textit{J. M. Pollard} [Math. Comput. 32, 918--924 (1978; Zbl 0382.10001)] is so called because Pollard suggested the parallelism with the catch of a wild kangaroo using a tame one (the method is also known as \textit{lambda} method, because the paths of the two kangaroos look like that Greek letter). The running time of the kangaroo method is \(O(\sqrt N)\), with \(N\) the order of the group and it requires little storage. As \textit{P. C. van Oorschot} an \textit{M. J. Wiener} pointed out [J. Cryptology 12, 1--28 (1999; Zbl 0992.94028)], the method can be parallelized, using \(n\) instead of two kangaroos, the parallelized version providing a linear speed up. The present paper discusses in detail some theoretical and practical aspect of this parallelization. After a description of the kangaroo method and the two parallelized versions of van Oorschot-Wiener and Pollard the paper focus in the study of the appropriate choice of parameters and the analysis of the running time. Section 8. `Experimental results' shows the performance of the studied methods in a concrete case: the group of rational points of the elliptic curve \(y^2=x^3+5x+19\) over the prime field \(F_p\), \(p=10^{15}+37\). The paper finishes (section 9) with a discussion of applications and open problems.