Speeding Up Elliptic Curve Discrete Logarithm Computations with Point Halving

Fangguo Zhang; Ping Wang

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: 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},
      url = {https://eprint.iacr.org/2011/461}
}