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 2¹⁷²5³⁷⁸ = 1010 = 2³⁰¹5⁴¹⁶(mod 1019)

2¹⁷²5³⁷⁸(mod 1019) does not equal 1010; it equals 9. 2³⁰¹5⁴¹⁶(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 2¹⁷²5³⁷⁸ = − 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)