On the optimal passing of distinguished points for parallelized Pollard’s rho-method :: IKBFU's united scientific journal editorial office


Forgot your password?
Login As
You can log in if you are registered at one of these services:
The supreme embodiment of reason is science
Ivan P. Pavlov

DOI-generator Search by DOI on Crossref.org

On the optimal passing of distinguished points for parallelized Pollard’s rho-method

Author Perevoshchikov V. V.
Pages 68-74
Article Download
Keywords discrete logarithm, Pollard’s rho-method, elliptic curves, parallel programming, random walk.
Abstract (summary) Problems of development and realization of an efficient parallelized algorithm to solve elliptic curve discrete logarithm problem (ECDLP) based on Pollard’s rho-method in the computational model SPMD using technology of message passing are considered. It is researched how many central processes are needed and what proportion of distinguished points is needed to be set to optimize an expected working time of this algorithm under the constraints of available memory; analyses the testing results of the developed program.

1. Van Oorschot P., Wiener M. Parallel collision search with cryptanalytic appli­ca­tions // J. of Cryptology. 1999. 12(1).

2. Hankerson D., Menezes A., Vanstone S. Guide to elliptic curve cryptography.
N.-Y., 2004.

3. Kuhn F., Struik R. Random walks revisited: extensions of Pollard’s rho al­go­rithm for computing multiple discrete logarithms // 8th Annual Workshop on Se­lected Areas in Cryptography. Toronto, 2001.

4. Кнут Д. Э. Искусство программирования. Т. 3: Сортировка и поиск.
М., 2008.

5. Перевощиков В. В., Гриценко А. А. Об эффективной реализации дискрет­ного логарифмирования на эллиптических кривых // Научная сессия ТУСУР. Т. 3: Системная интеграция и безопасность. Томск, 2009.

Back to the section