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

D.J. Bernstein; T. Lange; P. Schwabe

doi:10.1007/978-3-642-19379-8_8

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

D.J. Bernstein
, T. Lange
, P. Schwabe

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

31 Citations (Scopus)

2 Downloads (Pure)

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.

Original language	English
Title of host publication	Public Key Cryptography - PKC 2011 (14th International Conference on Practice and Theory in Public-Key Cryptography, Taormina, Italy, March 6-9, 2011. Proceedings)
Editors	D. Catalano, N. Fazio, R. Gennaro, A. Nicolosi
Place of Publication	Berlin
Publisher	Springer
Pages	128-146
ISBN (Print)	978-3-642-19378-1
DOIs	https://doi.org/10.1007/978-3-642-19379-8_8
Publication status	Published - 2011

Publication series

Name	Lecture Notes in Computer Science
Volume	6571
ISSN (Print)	0302-9743

Access to Document

10.1007/978-3-642-19379-8_8

http://eprint.iacr.org/2011/003

Cite this

Bernstein, D. J., Lange, T., & Schwabe, P. (2011). On the correct use of the negation map in the Pollard rho method. In D. Catalano, N. Fazio, R. Gennaro, & A. Nicolosi (Eds.), Public Key Cryptography - PKC 2011 (14th International Conference on Practice and Theory in Public-Key Cryptography, Taormina, Italy, March 6-9, 2011. Proceedings) (pp. 128-146). (Lecture Notes in Computer Science; Vol. 6571). Springer. https://doi.org/10.1007/978-3-642-19379-8_8

Bernstein, D.J. ; Lange, T. ; Schwabe, P. / On the correct use of the negation map in the Pollard rho method. Public Key Cryptography - PKC 2011 (14th International Conference on Practice and Theory in Public-Key Cryptography, Taormina, Italy, March 6-9, 2011. Proceedings). editor / D. Catalano ; N. Fazio ; R. Gennaro ; A. Nicolosi. Berlin : Springer, 2011. pp. 128-146 (Lecture Notes in Computer Science).

@inproceedings{38aedacffbc648f194190dfcc405880a,

title = "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{\textquoteright}s rho method that fully exploits the negation map without branching, and secondarily from improved techniques for modular arithmetic.",

author = "D.J. Bernstein and T. Lange and P. Schwabe",

year = "2011",

doi = "10.1007/978-3-642-19379-8\_8",

language = "English",

isbn = "978-3-642-19378-1",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "128--146",

editor = "D. Catalano and N. Fazio and R. Gennaro and A. Nicolosi",

booktitle = "Public Key Cryptography - PKC 2011 (14th International Conference on Practice and Theory in Public-Key Cryptography, Taormina, Italy, March 6-9, 2011. Proceedings)",

address = "Germany",

}

Bernstein, DJ, Lange, T & Schwabe, P 2011, On the correct use of the negation map in the Pollard rho method. in D Catalano, N Fazio, R Gennaro & A Nicolosi (eds), Public Key Cryptography - PKC 2011 (14th International Conference on Practice and Theory in Public-Key Cryptography, Taormina, Italy, March 6-9, 2011. Proceedings). Lecture Notes in Computer Science, vol. 6571, Springer, Berlin, pp. 128-146. https://doi.org/10.1007/978-3-642-19379-8_8

On the correct use of the negation map in the Pollard rho method. / Bernstein, D.J.; Lange, T.; Schwabe, P.
Public Key Cryptography - PKC 2011 (14th International Conference on Practice and Theory in Public-Key Cryptography, Taormina, Italy, March 6-9, 2011. Proceedings). ed. / D. Catalano; N. Fazio; R. Gennaro; A. Nicolosi. Berlin: Springer, 2011. p. 128-146 (Lecture Notes in Computer Science; Vol. 6571).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Bernstein, D.J.

AU - Lange, T.

AU - Schwabe, P.

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-642-19379-8_8

DO - 10.1007/978-3-642-19379-8_8

M3 - Conference contribution

SN - 978-3-642-19378-1

T3 - Lecture Notes in Computer Science

SP - 128

EP - 146

BT - Public Key Cryptography - PKC 2011 (14th International Conference on Practice and Theory in Public-Key Cryptography, Taormina, Italy, March 6-9, 2011. Proceedings)

A2 - Catalano, D.

A2 - Fazio, N.

A2 - Gennaro, R.

A2 - Nicolosi, A.

PB - Springer

CY - Berlin

ER -

Bernstein DJ, Lange T, Schwabe P. On the correct use of the negation map in the Pollard rho method. In Catalano D, Fazio N, Gennaro R, Nicolosi A, editors, Public Key Cryptography - PKC 2011 (14th International Conference on Practice and Theory in Public-Key Cryptography, Taormina, Italy, March 6-9, 2011. Proceedings). Berlin: Springer. 2011. p. 128-146. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-19379-8_8

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

Abstract

Publication series

Access to Document

Fingerprint

Cite this