Two grumpy giants and a baby

Daniel J.  Bernstein; Tanja Lange

Paper 2012/294 Original: eprint.iacr.org/2012/294 ↗

Two grumpy giants and a baby

Daniel J. Bernstein

Tanja Lange

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

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
History: 2012-07-10: last updated; 2012-06-03: published
Short URL: https://ia.cr/2012/294
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2012/294,
      author = {Daniel J.  Bernstein and Tanja Lange},
      title = {Two grumpy giants and a baby},
      howpublished = {Cryptology {ePrint} Archive, Paper 2012/294},
      year = {2012},
      url = {https://eprint.iacr.org/2012/294}
}