# Pollard's Rho - Constructing the random function

Suppose we are aiming to solve the discrete logarithm problem $$\alpha^x=\beta$$ in some cyclic group $$G=<\alpha>$$. Then we are looking for a (uniformly) random sequence of elements of the form $$\alpha^{a_{i}}\beta^{b_{i}}$$, $$i=0,1,2,...$$ so that we can invoke the 'Birthday Paradox'. Pollard suggested a function which apparently works fairly well but can be improved on.

My question concerns the concrete implementation of Pollard's Rho: if we generated sequences of integers $$\{a_{i}\}$$, $$\{b_{i}\}$$ with a random number generator (from any given programming language), would this yield an acceptable 'level of randomness'?

The reason I am asking this is because I stumbled upon articles on 'random walks' for pollard's rho, which all seemed rather extensive; this led me to believe that achieving an desired level of randomness is quite tricky, and that there is a flaw in my idea of generating random integers. However, I can't seem to find it.

• Please add some references to the "extensive articles" so I can check them out. – Barack Obama Sep 16 '14 at 21:26
• I first stumbled upon ''On the Eﬃciency of Pollard’s Rho Method for Discrete Logarithms'' by Brent and Bai. This paper refers to other papers by Teske, who presented a improvement of Pollard's original function in ''On Random Walks for Pollard's Rho Method''. – polarbear Sep 17 '14 at 9:48

If you generate group elements at random as you suggest then you can indeed invoke the "Birthday Paradox" to find logarithms in time $O(\sqrt p)$. Unfortunately your storage requirements are the same and for cryptographically interesting group orders your method is therefore far from optimal.