Computing discrete logarithms with the parallelized kangaroo method

✍ Scribed by Edlyn Teske

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 241 KB
• Volume: 130
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(02)00590-5

✦ Synopsis

The Pollard kangaroo method computes discrete logarithms in arbitrary cyclic groups. It is applied if the discrete logarithm is known to lie in a certain interval, say [a; b], and then has expected running time O( √ b -a) group operations. In its serial version it uses very little storage. It can be parallelized with linear speed-up, and in its parallelized version its storage requirements can be e ciently monitored. This makes the kangaroo method the most powerful method to solve the discrete logarithm problem in this situation. In this paper, we discuss various experimental and theoretical aspects of the method that are important for its most e ective application.