Talk:Pollard's rho algorithm for logarithms

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
Low	This article has been rated as Low-priority on the project's priority scale.

Computer science

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles

???

This article has not yet received a rating on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]