Collision Bounds for the Additive Pollard Rho Algorithm for Solving Discrete Logarithms

We prove collision bounds for the Pollard rho algorithm to solve the discrete logarithm

problem in a general cyclic group G. Unlike the setting studied by Kim et al., we consider additive walks: the setting used in practice to solve the elliptic curve discrete logarithm problem. Our bounds differ from the birthday bound O(sqrt(|G|)) by a factor of sqrt(\log(|\G|)) and are based on mixing time estimates for random walks on finite abelian groups due to Dou and Hildebrand.