0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Please add some references to the "extensive articles" so I can check them out. $\endgroup$ – Barack Obama Sep 16 '14 at 21:26
  • $\begingroup$ I first stumbled upon ''On the Efficiency 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''. $\endgroup$ – polarbear Sep 17 '14 at 9:48
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.