# Pollard’s Rho Method

I can't get my head around Pollard’s Rho Method for solving discrate log problem

I have read in a book:

The basic idea is to pseudorandomly generate group elements of the form α^i · β^j

So,what are i and j

We continue until we obtain a collision of two elements, i.e., until we have α^i1 · β^j1 = α^i2 · β^j2

Why does finding a collision mean that we have solved the problem??

I understand Pollard’s Rho Method for factorization ,but I can't see how it's similar to Pollard’s Rho Method for solving discrate log

Why does finding a collision mean that we have solved the problem?

If we find a collision:

$\alpha^{i1} \cdot \beta^{j1} = \alpha^{i2} \cdot \beta^{j2}$

then we know that:

$\alpha^{i1-i2} = \beta^{j2-j1}$

And so, if we know the order of the group (which we generally do), then we can compute $({i1-i2})^{-1}$, and so, we have:

$\alpha = \beta^{(j2-j1) \cdot ({i1-i2})^{-1}}$

Here's that idea behind the Rho method: if we designate $F^n(x)$ as the function $F$ iterated $n$ times, for example, $F^4(x) = F(F(F(F(x))))$, and $F$ as a finite range of size $\lambda$, then $F^n(x) = F^{2n}(x)$ for some $n$. In addition, if $F$ is a random function, then $n$ will (with good probability) be $O(\sqrt{\lambda})$. This allows us to search for a collision with a small amount of memory (and at a constant cost factor over more obvious techniques that do use a table for $F$ values).