Kangaroos, monopoly and discrete logarithms (Q1590361)

The Pollard ``rho'' and ``kangaroo'' methods for finding the discrete logarithm in any cyclic group are discussed. For the rho method, the order of the group, \(g\), must be known and it runs in \(O(q^{1/2})\) time where \(q\) is the largest prime divisor of \(g\). For the kangaroo method, it is not necessary to know \(g\) but only that it lies in some interval of width \(w\). The time of the algorithm is \(O(w^{1/2})\). Parallel versions of both algorithms are available. This paper improves the analysis of the running time of the kangaroo method for both serial and parallel versions to solve the problem \[ r^z = q ,\quad L \leq z \leq U, \quad w = U-L . \] In particular, the paper examines the effect of the choice of the set of jumps of the kangaroos \[ S = \{ s_1 , s_2 , \cdots , s_k \} \] (which may contain repetitions), ordered in nondecreasing order. The relationship of the problem to some calculations of interest to players of monopoly and to a card trick due to Kruskal is discussed.