How long does it take to catch a wild kangaroo?

ABSTRACT

The discrete logarithm problem asks to solve for the exponent x, given the generator g of a cyclic group G and an element h∈ G such that g^x=h. We give the first rigorous proof that Pollard's Kangaroo method finds the discrete logarithm in expected time (3+o(1))√{b-a} for the worst value of x∈[a,b], and (2+o(1))√b-a when x∈_uar[a,b]. This matches the conjectured time complexity and, rare among the analysis of algorithms based on Markov chains, even the lead constants 2 and 3 are correct.

REFERENCES

• 1: D. Boneh and X. Boyen, "Short Signatures Without Random Oracles," Proc. of Eurocrypt 2004, LNCS 3027, pp. 56--73 (2004).
• 2: J-H. Kim, R. Montenegro, Y. Peres and P. Tetali, "A Birthday Paradox for Markov chains, with an optimal bound for collision in the Pollard Rho Algorithm for Discrete Logarithm," Proc. of the 8th Algorithmic Number Theory Symposium (ANTS-VIII), Springer LNCS vol. 5011, pp. 402--415 (2008).
• 3: J. Lagarias, E. Rains and R.J. Vanderbei, "The Kruskal Count," in The Mathematics of Preference, Choice and Order. Essays in Honor of Peter J. Fishburn,(Stephen Brams, William V. Gehrlein and Fred S. Roberts, Eds.), Springer-Verlag: Berlin Heidelberg, pp. 371--391 (2009).
• 4: S. Miller and R. Venkatesan, "Spectral Analysis of Pollard Rho Collisions," Proc. of the 7th Algorithmic Number Theory Symposium (ANTS-VII), Springer LNCS vol. 4076, pp. 573--581 (2006).
• 5: P.C. van Oorschot and M.J. Wiener, "Parallel collision search with cryptanalytic applications," Journal of Cryptology, vol. 12 no. 1, pp. 1--28 (1999).
• 6: J. Pollard, "Monte Carlo methods for index computation mod p," Mathematics of Computation, vol. 32 no. 143, pp. 918--924 (1978).
• 7: J. Pollard, "Kangaroos, Monopoly and Discrete Logarithms," Journal of Cryptology, vol. 13 no. 4, pp. 437--447 (2000).
• 8: E. Teske, "Square-root Algorithms for the Discrete Logarithm Problem (A Survey)," in Public-Key Cryptography and Computational Number Theory,Walter de Gruyter, Berlin - New York, pp. 283--301 (2001).

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Theory

Keywords:
digital signature, discrete logarithm, markov chain, mixing time, pollard's kangaroo method