An Efficient Collision Detection Method for Computing Discrete Logarithms with Pollard's Rho
Joint Authors
Source
Journal of Applied Mathematics
Issue
Vol. 2012, Issue 2012 (31 Dec. 2012), pp.1-15, 15 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2012-01-16
Country of Publication
Egypt
No. of Pages
15
Main Subjects
Abstract EN
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.
American Psychological Association (APA)
Wang, Ping& Zhang, Fangguo. 2012. An Efficient Collision Detection Method for Computing Discrete Logarithms with Pollard's Rho. Journal of Applied Mathematics،Vol. 2012, no. 2012, pp.1-15.
https://search.emarefa.net/detail/BIM-993439
Modern Language Association (MLA)
Wang, Ping& Zhang, Fangguo. An Efficient Collision Detection Method for Computing Discrete Logarithms with Pollard's Rho. Journal of Applied Mathematics No. 2012 (2012), pp.1-15.
https://search.emarefa.net/detail/BIM-993439
American Medical Association (AMA)
Wang, Ping& Zhang, Fangguo. An Efficient Collision Detection Method for Computing Discrete Logarithms with Pollard's Rho. Journal of Applied Mathematics. 2012. Vol. 2012, no. 2012, pp.1-15.
https://search.emarefa.net/detail/BIM-993439
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-993439