Cryptology ePrint Archive: Report 2011/003

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

Daniel J. Bernstein and 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.

Category / Keywords: public-key cryptography / Elliptic curves, discrete-logarithm problem, negation map, branchless algorithms, SIMD

Publication Info: Expanded version of PKC 2011 paper.

Date: received 1 Jan 2011

Contact author: tanja at hyperelliptic org

Available format(s): PDF | BibTeX Citation

Version: 20110105:023104 (All versions of this report)

Short URL: ia.cr/2011/003

Discussion forum: Show discussion | Start new discussion