Pollard’s Rho Method

Question

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

Answer 1

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