Pollard's rho algorithm for logarithms

Pollard's rho algorithm for logarithms is a method introduced by John Pollard in 1978 for solving the discrete logarithm problem, and it is the analogue of his rho algorithm for integer factorization. The aim is to find the exponent gamma such that alpha raised to gamma equals beta, where beta lies in a cyclic group generated by alpha. The algorithm looks for two different representations of one group element, written as powers of alpha and beta, which gives a linear congruence in gamma that the extended Euclidean algorithm then solves. To find the collision it walks a pseudorandom sequence and uses Floyd's cycle-finding algorithm to detect when the sequence enters a loop. A common way to build the walk is to split the group into three roughly equal parts with a hash function and, depending on the part, double both tracked exponents or increment one of them. The article states that the running time is about the square root of the group order, and that combining the method with the Pohlig-Hellman algorithm reduces the cost to the square root of the largest prime factor of the order.