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.