Pollard's Rho - Constructing the Random Function

Question

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.

Answer 1

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.

The fastest way for groups with (apparently) no exploitable structure (like elliptic curves) uses "distinguished points" as it allows you to tailor your parameters to suit the storage you have available. Then there are issues relating to whether you're just finding one discrete logarithm or many.

Having said that, I believe that pretty well any reasonable random number generator will be satisfactory for your method. If a particular method of generating random numbers had a performance consistently different from normal then that would probably be of independent mathematical interest, worthy of publication.