Pollard’s rho algorithm

Pollard’s rho algorithm works like this: Suppose we have a successor function that defines a sequence that ends in a cycle. The object is to find the beginning of the cycle in the sequence. For example:

	a0->a1->a2->a3->a4->a5->a6->a3

Now we start two sequences, one using single steps and one using double steps. When the first sequence takes m steps it arrives at the entry point into the cycle, and the second sequence has moved m points beyond the entry point. When the first sequence moves n-m steps from the entry point the second moves 2(n-m) from m points past the entry point. Both are then at the same point in the cycle, namely m points before the entry points. Call this point the intersection point.

We now do two single step sequences, one from the original starting point, and one from the intersection point. In m steps both arrive at the entry point. Here is how it works in our example:

Pass 1:
seq 1:  a0-a1-a2-a3-a4
seq 2:  a0-a2-a4-a6-a4
Pass 2:
seq 1:  a0-a1-a2-a3
seq 2:  a4-a5-a6-a3