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 gx=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.

We analyze-a fairly standard idealization of Pollard's rho algorithm for finding the discrete logarithm in acyclic group G. It is found that, with high probability, a collision occurs in O(radic( |G|log|G|log log|G|)) steps, not far from the widely conjectured value of Theta(radic|G|). Tins improves upon a recent result of Miller-Venkalesan which showed an upper bound of O(radic|G|log3|G|). Our proof is based on analyzing an appropriate nonreversible, non-lazy random walk on a discrete cycle of (odd) length |G|, and showing that the mixing time of the corresponding walk is O(log|G|log log|G|).

We show how to bound the mixing time and log-Sobolev constants of Markov chains by bounding the edge-isoperimetry of their underlying graphs. To do this we use two recent techniques, one involving Average Conductance and the other log-Sobolev constants. We show a sort of strong conductance bound on a family of geometric Markov chains, give improved bounds for the mixing time of a Markov chain on balanced matroids, and in both cases find lower bounds on the log-Sobolev constants of these chains.