Talk:Pollard's rho algorithm for logarithms
From Wikipedia, the free encyclopedia
I don't totally understand this algorithm yet, but the bottom of the page says:
- That is 21725378 = 1010 = 23015416(mod 1019)
21725378(mod 1019) does not equal 1010; it equals 9. 23015416(mod 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 
). That's why 21725378 = − 1010 = 9(mod 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 
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)
[edit] Redirect
Hi, as far as I know, Pollard created two Ρ(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)
[edit] 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)
