Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 5 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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