Paper 2011/003

On the correct use of the negation map in the Pollard rho method

Daniel J. Bernstein, Tanja Lange, and Peter Schwabe

Abstract

Bos, Kaihara, Kleinjung, Lenstra, and Montgomery recently showed that ECDLPs on the 112-bit secp112r1 curve can be solved in an expected time of 65 years on a PlayStation 3. This paper shows how to solve the same ECDLPs at almost twice the speed on the same hardware. The improvement comes primarily from a new variant of Pollard's rho method that fully exploits the negation map without branching, and secondarily from improved techniques for modular arithmetic.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Expanded version of PKC 2011 paper.
Keywords
Elliptic curvesdiscrete-logarithm problemnegation mapbranchless algorithmsSIMD
Contact author(s)
tanja @ hyperelliptic org
History
2011-01-05: received
Short URL
https://ia.cr/2011/003
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/003,
      author = {Daniel J.  Bernstein and Tanja Lange and Peter Schwabe},
      title = {On the correct use of the negation map in the Pollard rho method},
      howpublished = {Cryptology ePrint Archive, Paper 2011/003},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/003}},
      url = {https://eprint.iacr.org/2011/003}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.