Two grumpy giants and a baby

D.J. Bernstein, T. Lange

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

1 Downloads (Pure)


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
Originele taal-2Engels
TitelANTS X (Proceedings of the Tenth Algorithmic Number Theory Symposium, San Diego, California, July 9-13, 2012)
RedacteurenE.W. Howe, K.S. Kedlaya
Plaats van productieBerkeley
UitgeverijMathematical Sciences Publishers
ISBN van geprinte versie978-1-935107-00-2
StatusGepubliceerd - 2013
Evenement10th Algorithmic Number Theory Symposium (ANTS 2012) - University of California, San Diego, Verenigde Staten van Amerika
Duur: 9 jul. 201213 jul. 2012
Congresnummer: 10

Publicatie series

NaamThe Open Book Series
ISSN van geprinte versie2329-9061


Congres10th Algorithmic Number Theory Symposium (ANTS 2012)
Verkorte titelANTS X
Land/RegioVerenigde Staten van Amerika
StadSan Diego
AnderTenth Algorithmic Number Theory Symposium


Duik in de onderzoeksthema's van 'Two grumpy giants and a baby'. Samen vormen ze een unieke vingerafdruk.

Citeer dit