The kangaroo in question is Pollard’s kangaroo (or lambda method) [1], in the distinguished points variant [2]. The eponymous feature of the method is that it has two kangaroos, one tame (or known) and one wild, that make (pseudo-)random jumps in a cyclic group G, where the jump sizes come from a set S. If the wild kangaroo ever lands on a point where the tame kangaroo has been, their paths from then on are the same, and the method can be used to find where the wild kangaroo starts, which is normally the value of a desired discrete logarithm.

This method is best applied where the discrete logarithm x is assumed to lie in some interval [a,b]. The paper shows that the number of group operations is (3 + o(1)) if x = a or b, and is otherwise bounded by this. Furthermore, if x is uniformly random in [a,b], the average number is (2 + o(1)) .

There is a subtlety in the bullet point spanning the column break on page 554: “We consider powers of two, S = {2^k}^d_{k=0}, with d ≈ log₂ + log₂ log₂ - 2.” For a realistic b - a, say 2³⁰ or more, this seems possible. While the first equation of Section 4 is an example, some details need to be filled in to get the approximation; in particular, the - 2 term seems crucial.

The paper uses some notation with which I am unfamiliar: 1_C is not explained, but is “1 if C is true, otherwise 0.” It also falls into the common trap of declaring that cryptographic schemes are “all based on an assumption that discrete logarithm is difficult to find.” It is possible--but unlikely--that some or all of these schemes would fail anyway, since their hypotheses are stronger than the general discrete logarithm.