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

Ping Wang and Fangguo Zhang

Journal of Applied Mathematics, 2012, vol. 2012, issue 1

Abstract: 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.309G to 1.295G under the same space requirements for the single rho method.

Date: 2012
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1155/2012/635909

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:jnljam:v:2012:y:2012:i:1:n:635909

Access Statistics for this article

More articles in Journal of Applied Mathematics from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().