Paper 2011/003 Original: eprint.iacr.org/2011/003 ↗
On the correct use of the negation map in the Pollard rho method
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
- Preprint.
- History
- 2011-01-05: last updated
- 2011-01-05: published
- Short URL
- https://ia.cr/2011/003
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}