Two grumpy giants and a baby

D.J. Bernstein; T. Lange

doi:10.2140/obs.2013.1.87

Two grumpy giants and a baby

D.J. Bernstein
, T. Lange

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

1 Downloads (Pure)

Abstract

Pollard's rho algorithm, along with parallelized, vectorized, and negating variants, is the standard method to compute discrete logarithms in generic prime-order groups. This paper presents two reasons that Pollard's rho algorithm is farther from optimality than generally believed. First, ``higher-degree local anti-collisions'' make the rho walk less random than the predictions made by the conventional Brent--Pollard heuristic. Second, even a truly random walk is suboptimal, because it suffers from ``global anti-collisions'' that can at least partially be avoided. For example, after (1.5+o(1))\sqrt(l) additions in a group of order l (without fast negation), the baby-step-giant-step method has probability 0.5625+o(1) of finding a uniform random discrete logarithm; a truly random walk would have probability 0.6753\ldots+o(1); and this paper's new two-grumpy-giants-and-a-baby method has probability 0.71875+o(1). Keywords: Pollard rho, baby-step giant-step, discrete logarithms, complexity

Original language	English
Title of host publication	ANTS X (Proceedings of the Tenth Algorithmic Number Theory Symposium, San Diego, California, July 9-13, 2012)
Editors	E.W. Howe, K.S. Kedlaya
Place of Publication	Berkeley
Publisher	Mathematical Sciences Publishers
Pages	87-111
ISBN (Print)	978-1-935107-00-2
DOIs	https://doi.org/10.2140/obs.2013.1.87
Publication status	Published - 2013
Event	10th Algorithmic Number Theory Symposium (ANTS 2012) - University of California, San Diego, United States Duration: 9 Jul 2012 → 13 Jul 2012 Conference number: 10

Publication series

Name	The Open Book Series
Volume	1
ISSN (Print)	2329-9061

Conference

Conference	10th Algorithmic Number Theory Symposium (ANTS 2012)
Abbreviated title	ANTS X
Country/Territory	United States
City	San Diego
Period	9/07/12 → 13/07/12

Access to Document

10.2140/obs.2013.1.87

http://eprint.iacr.org/2012/294

Cite this

@inproceedings{599a130b4fbd4f71ab20ef6259751e4b,

title = "Two grumpy giants and a baby",

abstract = "Pollard's rho algorithm, along with parallelized, vectorized, and negating variants, is the standard method to compute discrete logarithms in generic prime-order groups. This paper presents two reasons that Pollard's rho algorithm is farther from optimality than generally believed. First, ``higher-degree local anti-collisions'' make the rho walk less random than the predictions made by the conventional Brent--Pollard heuristic. Second, even a truly random walk is suboptimal, because it suffers from ``global anti-collisions'' that can at least partially be avoided. For example, after (1.5+o(1))\textbackslash{}sqrt(l) additions in a group of order l (without fast negation), the baby-step-giant-step method has probability 0.5625+o(1) of finding a uniform random discrete logarithm; a truly random walk would have probability 0.6753\textbackslash{}ldots+o(1); and this paper's new two-grumpy-giants-and-a-baby method has probability 0.71875+o(1). Keywords: Pollard rho, baby-step giant-step, discrete logarithms, complexity",

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

year = "2013",

doi = "10.2140/obs.2013.1.87",

language = "English",

isbn = "978-1-935107-00-2",

series = "The Open Book Series",

publisher = "Mathematical Sciences Publishers",

pages = "87--111",

editor = "E.W. Howe and K.S. Kedlaya",

booktitle = "ANTS X (Proceedings of the Tenth Algorithmic Number Theory Symposium, San Diego, California, July 9-13, 2012)",

address = "United States",

note = "10th Algorithmic Number Theory Symposium (ANTS 2012), ANTS X ; Conference date: 09-07-2012 Through 13-07-2012",

}

Bernstein, DJ & Lange, T 2013, Two grumpy giants and a baby. in EW Howe & KS Kedlaya (eds), ANTS X (Proceedings of the Tenth Algorithmic Number Theory Symposium, San Diego, California, July 9-13, 2012). The Open Book Series, vol. 1, Mathematical Sciences Publishers, Berkeley, pp. 87-111, 10th Algorithmic Number Theory Symposium (ANTS 2012), San Diego, California, United States, 9/07/12. https://doi.org/10.2140/obs.2013.1.87

Two grumpy giants and a baby. / Bernstein, D.J.; Lange, T.
ANTS X (Proceedings of the Tenth Algorithmic Number Theory Symposium, San Diego, California, July 9-13, 2012). ed. / E.W. Howe; K.S. Kedlaya. Berkeley: Mathematical Sciences Publishers, 2013. p. 87-111 (The Open Book Series; Vol. 1).

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

TY - GEN

T1 - Two grumpy giants and a baby

AU - Bernstein, D.J.

AU - Lange, T.

N1 - Conference code: 10

PY - 2013

Y1 - 2013

N2 - Pollard's rho algorithm, along with parallelized, vectorized, and negating variants, is the standard method to compute discrete logarithms in generic prime-order groups. This paper presents two reasons that Pollard's rho algorithm is farther from optimality than generally believed. First, ``higher-degree local anti-collisions'' make the rho walk less random than the predictions made by the conventional Brent--Pollard heuristic. Second, even a truly random walk is suboptimal, because it suffers from ``global anti-collisions'' that can at least partially be avoided. For example, after (1.5+o(1))\sqrt(l) additions in a group of order l (without fast negation), the baby-step-giant-step method has probability 0.5625+o(1) of finding a uniform random discrete logarithm; a truly random walk would have probability 0.6753\ldots+o(1); and this paper's new two-grumpy-giants-and-a-baby method has probability 0.71875+o(1). Keywords: Pollard rho, baby-step giant-step, discrete logarithms, complexity

AB - Pollard's rho algorithm, along with parallelized, vectorized, and negating variants, is the standard method to compute discrete logarithms in generic prime-order groups. This paper presents two reasons that Pollard's rho algorithm is farther from optimality than generally believed. First, ``higher-degree local anti-collisions'' make the rho walk less random than the predictions made by the conventional Brent--Pollard heuristic. Second, even a truly random walk is suboptimal, because it suffers from ``global anti-collisions'' that can at least partially be avoided. For example, after (1.5+o(1))\sqrt(l) additions in a group of order l (without fast negation), the baby-step-giant-step method has probability 0.5625+o(1) of finding a uniform random discrete logarithm; a truly random walk would have probability 0.6753\ldots+o(1); and this paper's new two-grumpy-giants-and-a-baby method has probability 0.71875+o(1). Keywords: Pollard rho, baby-step giant-step, discrete logarithms, complexity

U2 - 10.2140/obs.2013.1.87

DO - 10.2140/obs.2013.1.87

M3 - Conference contribution

SN - 978-1-935107-00-2

T3 - The Open Book Series

SP - 87

EP - 111

BT - ANTS X (Proceedings of the Tenth Algorithmic Number Theory Symposium, San Diego, California, July 9-13, 2012)

A2 - Howe, E.W.

A2 - Kedlaya, K.S.

PB - Mathematical Sciences Publishers

CY - Berkeley

T2 - 10th Algorithmic Number Theory Symposium (ANTS 2012)

Y2 - 9 July 2012 through 13 July 2012

ER -

Two grumpy giants and a baby

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this