Another contribution of our paper is to give an analysis of the average-case running time of Bernstein and Lange's ``grumpy giants and a baby'' algorithm, and also to consider this algorithm in the case of groups with efficient inversion.
Our conclusion is that, in the fully-optimised context, both the interleaved BSGS and grumpy-giants algorithms have superior average-case running time compared with Pollard rho. Furthermore, for the discrete logarithm problem in an interval, the interleaved BSGS algorithm is considerably faster than the Pollard kangaroo or Gaudry-Schost methods.
Category / Keywords: public-key cryptography / baby-step giant-step, elliptic curve discrete logarithm, negation map Date: received 18 Jun 2015, last revised 10 Feb 2016 Contact author: s galbraith at auckland ac nz Available format(s): PDF | BibTeX Citation Version: 20160211:004241 (All versions of this report) Short URL: ia.cr/2015/605