Paper 2011/008

Computing Elliptic Curve Discrete Logarithms with the Negation Map

Ping Wang and Fangguo Zhang

Abstract

It is clear that the negation map can be used to speed up the computation of elliptic curve discrete logarithms with the Pollard rho method. However, the random walks defined on elliptic curve points equivalence class $\{\pm P\}$ used by Pollard rho will always get trapped in fruitless cycles. We propose an efficient alternative approach to resolve fruitless cycles. Besides the theoretical analysis, we also examine the performance of the new algorithm in experiments with elliptic curve groups. The experiment results show that we can achieve the speedup by a factor extremely close to $\sqrt{2}$, which is the best performance one can achieve in theory, using the new algorithm with the negation map.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
elliptic curve cryptosystem
Contact author(s)
isszhfg @ mail sysu edu cn
History
2011-01-05: received
Short URL
https://ia.cr/2011/008
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/008,
      author = {Ping Wang and Fangguo Zhang},
      title = {Computing Elliptic Curve Discrete Logarithms with the Negation Map},
      howpublished = {Cryptology ePrint Archive, Paper 2011/008},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/008}},
      url = {https://eprint.iacr.org/2011/008}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.