Talk:Pollard's rho algorithm

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)

"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?

Citing

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

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)

Brent's method requires more steps, but fewer computations per step, so it is indeed a fair bit faster. I can confirm Patrickkonsor's simulation results. Surprisingly, Brent's(?) modification that really speeds things up by decreasing the number of gcd steps is not mentioned here. Kuroyama (talk) 16:36, 14 March 2009 (UTC)

pseudo-random sequence

I don't think the algorithm will work with any pseudo-random sequence, as perhaps implied by this article. The pseudo-random sequence must have the property that f(x) mod p = f(x mod p) mod p, for any x and p, so that collisions in modulo-p space behave as expected.

Am I right? It's a while since I've done this kind of stuff in earnest. —Preceding unsigned comment added by G121 (talk • contribs) 13:28, 4 July 2008 (UTC)

Yes, the core ideas section needs rewriting. It does not include the fact that the value mod p can be calculated from value mod N, and we have a way of detecting a cycle mod p (which is the key concept). Here is a good description. Somebody with better command of English - please fix this. I just checked - non-polynomnial pseudo-random functions don`t work.

--Gozewson (talk) 23:48, 3 September 2008 (UTC)

Confusing Algorithm

Supposed Pollard's Rho Algorithm, Richard Brent Variant: Since (q) is always MOD (n), (g) can never equal (n) -- making steps 4 and 5 pointless. I have seen several Java implementation which mindlessly do with exact some thing! Still looking for the correct algorithm... bitRAKE (talk) 15:23, 11 July 2008 (UTC)

My mistake, (g) equals (n) when (q) is zero! Best source is Richard Brent's original paper: http://wwwmaths.anu.edu.au/~brent/pub/pub051.html , which also specifies proper selection of (m). Step 4 is the backtracking which attempts to catch a single divisor prior to the last outer loop iteration.

If (m) is too large (q) can collects all the divisors of (n) within a single iteration. This leads me to deduce that if step 4 fails an additional step can assume all the divisors were in the last iteration and find one. I will attempt to test this... bitRAKE (talk) 02:33, 12 July 2008 (UTC)

I found the pseudo-code in this forum thread easier to follow and implement, though I had to add a check for product becoming 0, which indicates all factors were found since the last check.Daggerbox (talk) 21:12, 4 October 2008 (UTC)

one key point is missing from the Core Idea section

While it's true that two numbers x and y are congruent modulo p with probability 0.5 after $1.177{\sqrt {p}}$ numbers have been randomly chosen, we still need a method to find such a pair without trying all the pairs. This relies on a property of $f()$, i.e., $f(x)=f(y)\mod p$ when $x=y\mod p$. 143.117.38.239 (talk) 10:59, 11 September 2009 (UTC)

when n is prime, then d is always 1?

"Note, as well, that this algorithm does not work when n is a prime number, since, in this case, d will be always 1." Correct me if i'm wrong but d could also be n, when n is prime. d = GCD(|x − y|, n) and when n is prime then d=1 if 0 < |x-y| < n. But if |x-y| = n, then the GCD is n and if x=n and y=0 then |x-y| is n - 'cause of the mod n this can't happen. But as of http://wiki.riteme.site/wiki/Greatest_common_divisor GCD(0,a)=|a|, so if |x-y| is 0 then GCD is n and this can happen when x=y.

Otherwise if d would always be 1 when n is prime, this algorithm found on http://de.wikipedia.org/wiki/Pollard-Rho-Methode could not work (it would not terminate), but it's working (if n is prime you still get "failure" but there d isn't 1):

1. x ← 2, y ← x; d ← 1
2. While d = 1:
   1. x ← f(x)
   2. y ← f(f(y))
   3. d ← ggT(|x − y|, n)
3. If 1 < d < n then return d.
4. If d = n then return failure.

Example: n=19, f(x)=x²+c (mod n), c=1. It starts with x=2, y=x=2, d=1. After 1. step: x=6, y=0, d=1. After 2. step: x=0, y=6, d=1. After 3. step: x=2, y=2, d=19. => 19 is prime and d isn't 1.

Complexity

The article uses O(n^1/4 polylog(n)) as the number of steps required to find a factor on a semiprime number, but polylog almost always gives imaginary or negative results - [1] - is there a correct formula? Nightgunner5 (talk) 00:09, 10 June 2010 (UTC)

Just adding my own two cents, I notice that also the order of the polylogarithm is not specified. I think I'll add a “citation needed” tag to the article. Hanche (talk) 06:28, 8 October 2010 (UTC)

It seems that in nowhere we mention this algorithm cannot be used to factorize 2^n - we should fix this. 207.46.55.31 (talk) 10:20, 5 July 2012 (UTC)

Not so

In the article, F₈ is said to be the eighth Fermat number. It is actually the ninth. — Preceding unsigned comment added by 86.180.121.13 (talk) 13:58, 23 September 2014 (UTC)

This has now been corrected.

attempted to update article

I made an attempt to update the article with a reference to the third edition of the CLRS test "Introduction to Algorithms" as well as post some working POSIX compliant C code but the editor is too complex and I don't see how to add anything to this article that would be readable. I am not about to spend a day learning how to add a simple reference or format fixed text code to a page. I can certainly add it in and then hope someone else cleans it up. blastwave (talk) 22:00, 6 December 2015 (UTC)

The reference you added looks reasonably formatted — thanks. I'm not convinced that this is a good place to add complete implementations, though — Wikipedia isn't really set up to work well as a code repository, and should be more about the idea of an algorithm than the details of coding it. Re your difficulty with the editor: are you using the GUI "Visual Editor", or the text editor for wiki-markup? You can change between the two in your preferences (the checkbox "Temporarily disable the visual editor while it is in beta" under "Editor" in the "Editing" tab); the Visual Editor is intended to be easier to use but I prefer the text editor. —David Eppstein (talk) 22:37, 6 December 2015 (UTC)

Some points of confusion

I found the article rather confusing, perhaps due to edits from multiple sources based on different variants of the algorithms. Here are something I want to see fixed:

• The algorithm shown does not match the example (2 -> 5 -> 26 -> 677 -> 871), or the explanation in the text. The algorithm in text uses the Floyd cycle detection algorithm, the the example and the explanation do not. Also, the 871 number seems to pop from nowhere.
• Since the text does not use Floyd cycle detection, it would appear that the algorithm will only work if the cycle is of length 1, which would completely nullify the benefit of the birthday paradox.
• The usage of the birthday paradox is not explained, which is crucial to the understanding of the algorithm. Uninteresting details, like the constant in the birthday paradox, is added for no reason.
• No explanation is given to the Floyd cycle detection algorithm. Readers with no previous knowledge of that algorithm would found the article impossible to digest.
• The name "rho algorithm" is explained twice in the article, for no obvious reason.
• The text "The randomizing function g(x) must be a polynomial modulo n, so that it will work both modulo p and modulo n. That is, so that g(x mod p) ≡ g(x) (mod p)." appear at the wrong place: instead of preparing the readers to understand why the algorithm work, it looks more like an afterthought.

I'd like to write an edit to fix these problems. Let me know if you don't like it.

Isaacto (talk) 01:09, 28 June 2017 (UTC)

I think you have good points. Bubba73 ^{You talkin' to me?} 01:51, 28 June 2017 (UTC)

My editing is done.

Isaacto (talk) 17:07, 28 June 2017 (UTC)