Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Oct 22, 2011 #1
    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[itex]_{1}[/itex] = x[itex]_{0}[/itex]. Then you look for a length-1 or -2 cycle by saving x[itex]_1[/itex] and look for a match between x[itex]_{1}[/itex] and x[itex]_{2}[/itex] or x[itex]_{3}[/itex]. Then you look for a cycle with length 1 to 4 by saving x[itex]_{3}[/itex] and comparing with x[itex]_{4}[/itex] through x[itex]_{7}[/itex]. Generally, in step k+1 you look for a cycle with length 1 to 2[itex]^k[/itex] by saving x[itex]_{2^k-1}[/itex] and comparing that with x[itex]_{2^k}[/itex] through x[itex]_{2^{k+1}-1}[/itex]. Is this correct?
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted