Journal of Applied Mathematics
Volume 2012 (2012), Article ID 635909, 15 pages
Research Article

An Efficient Collision Detection Method for Computing Discrete Logarithms with Pollard's Rho

School of Information Science and Technology, Sun Yat-sen University, Guangzhou 510006, China

Received 7 July 2011; Revised 15 November 2011; Accepted 21 November 2011

Academic Editor: Jacek Rokicki

Copyright © 2012 Ping Wang and Fangguo Zhang. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


Pollard's rho method and its parallelized variant are at present known as the best generic algorithms for computing discrete logarithms. However, when we compute discrete logarithms in cyclic groups of large orders using Pollard's rho method, collision detection is always a high time and space consumer. In this paper, we present a new efficient collision detection algorithm for Pollard's rho method. The new algorithm is more efficient than the previous distinguished point method and can be easily adapted to other applications. However, the new algorithm does not work with the parallelized rho method, but it can be parallelized with Pollard's lambda method. Besides the theoretical analysis, we also compare the performances of the new algorithm with the distinguished point method in experiments with elliptic curve groups. The experiments show that the new algorithm can reduce the expected number of iterations before reaching a match from 1.309 | 𝐺 | to 1.295 | 𝐺 | under the same space requirements for the single rho method.