We consider Pollard's rho method for discrete logarithm computation. Usuall
y, in the analysis of its running time the assumption is made that a random
walk in the underlying group is simulated. We show that this assumption do
es not hold for the walk originally suggested by Pollard: its performance i
s worse than in the random case. We study alternative walks that can be eff
iciently applied to compute discrete logarithms. We introduce a class of wa
lks that lead to the same performance as expected in the random case. We sh
ow that this holds for arbitrarily large prime group orders, thus making Po
llard's rho method for prime group orders about 20% faster than before.