2011
On random walks of Pollard's rho method for the ECDLP on Koblitz curves
JMI : journal of math-for-industry
- Volume
- 3
- Number
- 0
- First page
- 107
- Last page
- 112
- Language
- English
- Publishing type
- Publisher
- Faculty of Mathematics, Kyushu University
Pollard's rho method is the asymptotically fastest known attack for the elliptic curve discrete logarithm problem (ECDLP) except special cases. It works by giving a pseudo-random sequence defined by an iteration function and then detecting a collision in the sequence. We note that the number of iterations before obtaining a collision is significant for the running time of the rho method and depends on the choice of an iteration function. For many iteration functions suitable for the ECDLP on elliptic curves except Koblitz curves, the number of iterations before obtaining a collision had been investigated. In this paper, we propose a new iteration function on Koblitz curves which is an extension of the iteration function proposed by Gallant et al. and analyze the performance on our iteration function experimentally.
- Link information
- ID information
-
- ISSN : 1884-4774
- CiNii Articles ID : 40019161261
- CiNii Books ID : AA12444018