Paper 2012/294

Two grumpy giants and a baby

Daniel J. Bernstein and 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
Published elsewhere. Expanded version of ANTS 2012 paper.
Keywords
Discrete logarithmsPollard rhobaby-step giant-stepanticollisions
Contact author(s)
tanja @ hyperelliptic org
History
2012-07-10: revised
2012-06-03: received
See all versions
Short URL
https://ia.cr/2012/294
License
Creative Commons Attribution
CC BY

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},
      note = {\url{https://eprint.iacr.org/2012/294}},
      url = {https://eprint.iacr.org/2012/294}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.