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}}$

Tada, we're done.


  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


Actually, the similarity isn't in what you do when you find a collision, it's a clever way of searching for collisions without using a huge amount of memory.  

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).