Talk:Pollard's rho algorithm for logarithms

not necessarily subgroups

The first paragraph says "Divide $G$ into three subsets (not necessarily subgroups) of approximately equal size". As no two subgroups of any group $G$ are ever distinct, the remark does not make any sense. I would recommend removing it. Better explanation could be for instance: "Partition $G$ into three disjoint subsets $G_{0}$, $G_{1}$, and $G_{2}$ of approximately equal size. Note that these are not subgroups, as subgroups are never disjoint." Jsedenka (talk) 13:13, 4 May 2012 (UTC)

---

I don't totally understand this algorithm yet, but the bottom of the page says:

That is $2^{172}5^{378}=1010=2^{301}5^{416}{\pmod {1019}}$

$2^{172}5^{378}{\pmod {1019}}$ does not equal 1010; it equals 9. $2^{301}5^{416}{\pmod {1019}}$ does however equal 1010. Does anyone know what's going on here or know what to change to fix it? --Unclewalrus 18:54, 27 March 2006 (UTC)

Not sure what the person who originally write that was thinking. As you note it is blatantly false, and not claimed by the algorithm at all. I've corrected it to the proper claim from which the result should follow. Leland McInnes 21:44, 27 March 2006 (UTC)

The problem is that the order of 2 modulo 1019 is not 509 but 1018 (2 actually generates $\mathbb {F} _{1019}^{\star }$). That's why $2^{172}5^{378}=-1010=9{\pmod {1019}}$. Nonetheless, the changes in the following equation seem not correct, though the result seems the expected. Changing n in the C++-listings fixes this problem, the result ressemble the former one and the original statement holds. --Mattze 20:24, 28 June 2006 (UTC)

By writing $\gamma ={\frac {A-a}{b-B}}\mod n$ the author implied that there IS an unique inverse mod n which is in general only the case if n is prime. So γ is the solution of an equation mod n and might not be unique. (But there won't be that many solutions and one is the correct one) --Mattias Ulbrich 08:22, 29 June 2006 (UTC)

Redirect

Hi, as far as I know, Pollard created two $\mathrm {P}$(Rho)-algorithms, one for computing the Integer_factorization and one for computing the Discrete_logarithm. Both are documented in Menezes', Vanstone's and Oorshots's "Handbook of applied Cryptography". So we should get rid of this redirect and start an article stub, and rename the Pollard's_rho_algorithm article into something like Pollard's_rho_algorithm_for_factorization and make the original page a disambition page, I would suggest. I do not have the mathematical skills yet to write a good article containing Pollards Rho-Algorithm, so I'd first just do the structural stuff. We could just start with a stub and then fill it somehow. --Bjoern.thalheim 13:43, 23 September 2005 (UTC)

The functions changing a and b

Hi,

I was just wondering. In the functions g and h wouldn't you calculate the values for a and b mod (p - 1)? Because a and b are just the exponents of alpha and beta and when working mod p exponents cannot be larger than (p - 1).

Douglas Robinson 23:54, 29 December 2006 (UTC)

EDIT Now that I read through the article again I notice that this is done in the code in the section after the description.

Douglas Robinson 00:13, 30 December 2006 (UTC)

Complexity

I'm not particularly familiar with this algorithm, but shouldn't we be clearer and say the time complexity is sqrt(N) rather than sqrt(n), and perhaps emphasize that this is pseudo-polynomial, not polynomial, time... 71.194.163.223 21:48, 5 September 2007 (UTC)

I would move the estimated loop-detection length analysis under the complexity section, and detail the computation of this square root of pi times n over eight. Cilisso (talk) 10:27, 30 March 2023 (UTC)

Calculation of $\gamma$

The article says "we can calculate $\gamma$ as a solution of the equation $(B-b)\gamma =(a-A){\pmod {n}}$", but not *every* solution of this equation will be a solution to the discrete logarithm problem. This confused me at first, and the only reason I saw that we have to actually try multiple solutions is the example. The use of $p$ as group order in the algorithm suggests that it is prime, but it need not be (and is not required in article), and then the algorithm is wrong, because there is not necessarily a solution to $(B-b)\gamma =(a-A){\pmod {n}}$ (or is there in this case?), and even then it is not necessarily unique. — Preceding unsigned comment added by 145.116.189.186 (talk) 20:08, 16 November 2016 (UTC)

Notation

The notation in the article is inconsistent, sometimes using n for the group order and sometimes p. I'll switch it to n throughout unless anyone objects.2001:470:1F09:11ED:0:0:0:12 (talk) 16:20, 22 October 2020 (UTC)