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