Paper 2011/461

Speeding Up Elliptic Curve Discrete Logarithm Computations with Point Halving

Fangguo Zhang and Ping Wang

Abstract

Pollard rho method and its parallelized variants are at present known as the best generic algorithms for computing elliptic curve discrete logarithms. We propose new iteration function for the rho method by exploiting the fact that point halving is more efficient than point addition for elliptic curves over binary fields. We present a careful analysis of the alternative rho method with new iteration function. Compared to the previous $r$-adding walk, generally the new method can achieve a significant speedup for computing elliptic curve discrete logarithms over binary fields. For instance, for certain NIST-recommended curves over binary fields, the new method is about 27\% faster than the previous best methods in single-instance Pollard rho method. When running several instances of Pollard rho method concurrently, and computing the inversions using the simultaneous inversion algorithm by Peter Montgomery, the new method is about 12-17\% faster than the previous best methods.

Note: More detail analysis for practice is added.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
isszhfg @ mail sysu edu cn
History
2011-11-30: last of 6 revisions
2011-08-29: received
See all versions
Short URL
https://ia.cr/2011/461
License
Creative Commons Attribution
CC BY

BibTeX

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