Search
Submit an article RU
Physics, mathematics, and technology

2010 Issue №10

Back to the list Download the article
Perevoshchikov V. V.

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

Pages
68-74
discrete logarithm Pollard’s rho-method elliptic curves parallel programming random walk.

Abstract

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.

Reference

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.