Thread: On Pollard Rho Cycle View Single Post
2020-09-16, 07:50   #7
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

3·112·29 Posts

Quote:
 Originally Posted by Deuterium Hello CR ! What an honour to have a reply from you !! So, since it's a "random algorithm" but works in a deterministic way (Birthday Paradox is helpful), what would be then the difference between using the classical Rho polynomial X^2+C instead of pure random numbers ? Just only because with pure random numbers between 1 and N will never fall in a cycle and since cycle detection leads to factorization this would be pointless ? So basically we need a "thing" (polynomial) that will inevitably fall in a cycle, sooner or later ? I make these confused and basic questions because in internet I have see many implementation of that C alghorithm that try to avoid the cycle, like getting a cycle is a bad thing... Another question : since C is a number that you can choose "freely", if for a choosen C you fall into a cycle and you do not obtain the factors, all you have is to change the C ? Or EVERY cycle you will fall in is always useful for getting the factor ? Thanks CR
Not all cycles are useful. If it has length N, for instance, it will report that a factor of N is N. For this reason some values of C are effectively useless.

Further, the trajectory of the values before they cycle can be short or long. For some, a priori unknown values the tail of the rho will be short and for others it will be long. This is just as pecial case of making a choice of the function to be iterated. One way of making Pollard rho a truly random algorithm is to run it in parallel on many processors, each of which are given a randomly chosen iterator. If you know of the ECM this approach should be familiar.