# Questions about Pollard's Rho and Brent's Cycle Finding

1. Oct 22, 2011

### MackTuesday

Hi, I'll get right to it:

1. Why is finding the cycle important in the Pollard rho factorization method? Is it so you know when to restart with different parameters?

2. Why use polynomials? Is it because they make passable pseudoprime generators? Or maybe it's because they end in a cycle?

3. I haven't seen a good explanation of Brent's cycle finding method. This is my guess as to how it works. You start by looking for a length-1 cycle by checking x$_{1}$ = x$_{0}$. Then you look for a length-1 or -2 cycle by saving x$_1$ and look for a match between x$_{1}$ and x$_{2}$ or x$_{3}$. Then you look for a cycle with length 1 to 4 by saving x$_{3}$ and comparing with x$_{4}$ through x$_{7}$. Generally, in step k+1 you look for a cycle with length 1 to 2$^k$ by saving x$_{2^k-1}$ and comparing that with x$_{2^k}$ through x$_{2^{k+1}-1}$. Is this correct?