Two grumpy giants and a baby

D.J. Bernstein, T. Lange

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-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 languageEnglish
Title of host publicationANTS X (Proceedings of the Tenth Algorithmic Number Theory Symposium, San Diego, California, July 9-13, 2012)
EditorsE.W. Howe, K.S. Kedlaya
Place of PublicationBerkeley
PublisherMathematical Sciences Publishers
Pages87-111
ISBN (Print)978-1-935107-00-2
DOIs
Publication statusPublished - 2013
Event10th Algorithmic Number Theory Symposium (ANTS 2012) - University of California, San Diego, United States
Duration: 9 Jul 201213 Jul 2012
Conference number: 10

Publication series

NameThe Open Book Series
Volume1
ISSN (Print)2329-9061

Conference

Conference10th Algorithmic Number Theory Symposium (ANTS 2012)
Abbreviated titleANTS X
CountryUnited States
CitySan Diego
Period9/07/1213/07/12

Cite this