Talk:Pollard's rho algorithm

From Wikipedia, the free encyclopedia

The algorithm under "Richard Brent's Variant" appears to have some problems. One problem is that 'm' is used but doesn't seem to be initialized. Where does it come from?

It states that 'm' is passed as input to the algorithm, such that 'm' > 0. Patrickkonsor (talk) 14:56, 17 May 2008 (UTC)

[edit] "Richard Brent's Variant" algorithm question

In Brent's original paper he wrote k=k+m. This appears as k=k+i on the Wikipedia page. Which is correct?

[edit] Citing

Note: The book "Introduction to Algorithms" uses brent's variant, not the original method.

[edit] Brent's algorithm

The algorithm presented here is /not/ faster than the original algorithm when implemented as presented. Can anyone show an implementation that actually is faster? Many books and docs say that it is faster but there is no substantiation... I would guess that it came from some old source and has been repeated over and over without being checked. A simple direct copy of the algorithms here into C++ leaves the Brent variant looking pointless...

Has anyone actually gotten this to be faster than the vanilla rho algorithm?

Jheriko (talk) 16:48, 2 January 2008 (UTC)

I have tested direct implementations of both of the algorithms given in the article, and the Richard Brent variant is indeed faster than the original algorithm. I had each algorithm factor the same randomly generated 80 bit semi primes. The Richard Brent variant was, on average, 47% faster than the original algorithm; although it does seem that the Richard Brent variant can get caught in an infinite loop without too much trouble. Patrickkonsor (talk) 14:56, 17 May 2008 (UTC)