Why does the Pollard Rho Method require random numbers and a function that behaves pseudo-randomly?

Question

I am following "Elliptic Curves: Number Theory and Cryptography" by Lawrence C Washington, and his example of using the Pollard Rho Method to solve the Elliptic Curve Discrete Logarithm Problem, which involves defining a pseudo-random iterative function and looking for cycles.

When introducing the function, he says

"Let G be a finite group of order N. Choose a function f:G→G that behaves rather randomly. Then start with a random element $P_0$ and compute the iterations $P_(i+1) = f(P_i)$. Since G is a finite set, there will be some indices $i_0<j_0$ such that $P_{(i_0)} =P_{(j_0)}$.

Then $P_{(i_0)+1} = f(P_{(i_0)} ) = f(P_{(j_0)}=P_{(j_0)+1}=$ and, similarly, $P_{(i_0)+l} = P_{(i_0)+l} $ for all l ≥ 0. Therefore, the sequence $P_i$ is periodic with period $j_0$ − $i_0$ (or possibly a divisor of $j_0$ − $i_0$)."

The bit I do not understand is what follows.

"If f is a randomly chosen random function (we’ll not make this precise), then we expect to find a match with $j_0$ at most a constant times ${\sqrt N}$. "

What effect does 'randomness' have on finding matches and the time needed to do so?

Answer 1

Couple of remarks:

1. A random $f$ is needed to avoid things like the following. Assume that $G$ is a cyclic group (happens often in elliptic curve crypto) with generator $g$, and use the (highly non-random) function $f(x)=gx$. Then we know in advance that $P_i=g^i$, and that we get the full period $N$. When that happens, we didn't help our cause at all.
2. But with a "random" function, the birthday paradox kicks in. If we randomly select $M$ elements of $G$, we are likely to begin to see repetitions, when $M$ is approximately $\sqrt{N}$ (give or take some small constant factor). The name birthday paradox comes from the fact in a crowd of slightly more than $\sqrt{365}$ people you often find two or more people who share a birthday.

The way Pollard $\rho$ is used to attack e.g. the discrete logarithm still requires the function $f$ to be defined in a useful way (to allow us to take advantage of the discovered period in solving the DLP). IIRC they partition the group $G$ into easily identifiable but random pieces. In each partition the function $f$ is given by a relatively simple formula depending on the partition. The randomness in $f$ then comes from the way the group $G$ is partitioned. See textbooks for the details.