An Efficient Collision Detection Method for Computing Discrete Logarithms with Pollard's Rho
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 s...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2012-01-01
|
| Series: | Journal of Applied Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2012/635909 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849395743236816896 |
|---|---|
| author | Ping Wang Fangguo Zhang |
| author_facet | Ping Wang Fangguo Zhang |
| author_sort | Ping Wang |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-a7aadcb712544caebaae294e6411ebdc |
| institution | Kabale University |
| issn | 1110-757X 1687-0042 |
| language | English |
| publishDate | 2012-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Applied Mathematics |
| spelling | doaj-art-a7aadcb712544caebaae294e6411ebdc2025-08-20T03:39:31ZengWileyJournal of Applied Mathematics1110-757X1687-00422012-01-01201210.1155/2012/635909635909An Efficient Collision Detection Method for Computing Discrete Logarithms with Pollard's RhoPing Wang0Fangguo Zhang1School of Information Science and Technology, Sun Yat-sen University, Guangzhou 510006, ChinaSchool of Information Science and Technology, Sun Yat-sen University, Guangzhou 510006, ChinaPollard'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.http://dx.doi.org/10.1155/2012/635909 |
| spellingShingle | Ping Wang Fangguo Zhang An Efficient Collision Detection Method for Computing Discrete Logarithms with Pollard's Rho Journal of Applied Mathematics |
| title | An Efficient Collision Detection Method for Computing Discrete Logarithms with Pollard's Rho |
| title_full | An Efficient Collision Detection Method for Computing Discrete Logarithms with Pollard's Rho |
| title_fullStr | An Efficient Collision Detection Method for Computing Discrete Logarithms with Pollard's Rho |
| title_full_unstemmed | An Efficient Collision Detection Method for Computing Discrete Logarithms with Pollard's Rho |
| title_short | An Efficient Collision Detection Method for Computing Discrete Logarithms with Pollard's Rho |
| title_sort | efficient collision detection method for computing discrete logarithms with pollard s rho |
| url | http://dx.doi.org/10.1155/2012/635909 |
| work_keys_str_mv | AT pingwang anefficientcollisiondetectionmethodforcomputingdiscretelogarithmswithpollardsrho AT fangguozhang anefficientcollisiondetectionmethodforcomputingdiscretelogarithmswithpollardsrho AT pingwang efficientcollisiondetectionmethodforcomputingdiscretelogarithmswithpollardsrho AT fangguozhang efficientcollisiondetectionmethodforcomputingdiscretelogarithmswithpollardsrho |