mersenneforum.org > Math Pollard Rho Discrete Log
 Register FAQ Search Today's Posts Mark Forums Read

 2012-09-23, 13:43 #1 rogue     "Mark" Apr 2003 Between here and the 24×7×61 Posts Pollard Rho Discrete Log I've implemented the Pollard Rho discrete log algorithm shown here, but I don't understand why it doesn't find a solution for 2^x = 5 mod 11. It clearly has a solution, but the algorithm doesn't find it. I've looked at C&P, although not thoroughly, and it is clear that the wiki is not complete, but it hasn't helped me determine why the algorithm fails. Can anyone here point me to what I'm doing wrong?
 2012-09-23, 16:10 #2 Raman Noodles     "Mr. Tuch" Dec 2007 Chennai, India 3·419 Posts t = g[SUP]l[/SUP] (mod p). The Pollard’s Rho approach can also be used to solve the Discrete Logarithm problem. Let xi = ta[SUB]i[/SUB]gb[SUB]i [/SUB](mod p) and a0 = 0, b0 = 0, x0 = 1. Here, we define a pseudo random function such as: (ai+1, bi+1) = (ai + 1 (mod φ(p)), bi), if 0 < xi < p/3 (ai+1, bi+1) = (2ai (mod φ(p)), 2bi (mod φ(p))), if p/3 < xi < 2p/3 (ai+1, bi+1) = (ai, bi + 1 (mod φ(p))), if 2p/3 < xi < p And so, we have that xi+1 = tx[SUB]i[/SUB] (mod p), if 0 < xi < p/3 xi+1 = xi2 (mod p), if p/3 < xi < 2p/3 xi+1 = gx[SUB]i[/SUB] (mod p), if 2p/3 < xi < p We compare the different values of xi to find out a match. Similar to the tortoise-hare algorithm (Floyd’s cycle finding algorithm), we compare x1 with x2, x2 with x4, x3 with x6 and so on. We compare xm with x2m each time, to look for a match. We have two variables for x, a and b, each of which hold the iterations for m and 2m respectively. If a match is found out, say xj = xk, then we have ta[SUB]j[/SUB]gb[SUB]j[/SUB] = ta[SUB]k[/SUB]gb[SUB]k[/SUB] (mod p). Since the period is φ(p), or a divisor of φ(p), comparing the powers of t and g, and writing t = gl, we will have (aj – ak).l ≡ bk – bj (mod φ(p)), from which we could calculate the value of l as to be l = (bk – bj)(aj – ak)-1 (mod φ(p)). Last fiddled with by Raman on 2012-09-23 at 16:22
 2012-09-23, 17:56 #3 rogue     "Mark" Apr 2003 Between here and the 1AB016 Posts You're obviously listing functions shown in C&P, which is different than the ones shown on the wiki. I have not implemented the C&P version (yet), but you didn't answer as to why the wiki variant doesn't work for the example I gave.
 2012-09-24, 05:36 #4 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 240068 Posts you may be doing something wrong there, the algorithm (pencil and paper version) works for 11, but you have to be careful as 3 and 5 are not generators for 11. If you use beta=5 from the provided piece of code, it will not work. Generators for 11 are 2, 6, 7, 8 only. Code: (12:35:22) gp > for(g=2,10, print1("g= "g" :\t"); for(i=1,10,print1(lift(Mod(g,11)^i)",\t ")); print()) g= 2 : 2, 4, 8, 5, 10, 9, 7, 3, 6, 1, g= 3 : 3, 9, 5, 4, 1, 3, 9, 5, 4, 1, g= 4 : 4, 5, 9, 3, 1, 4, 5, 9, 3, 1, g= 5 : 5, 3, 4, 9, 1, 5, 3, 4, 9, 1, g= 6 : 6, 3, 7, 9, 10, 5, 8, 4, 2, 1, g= 7 : 7, 5, 2, 3, 10, 4, 6, 9, 8, 1, g= 8 : 8, 9, 6, 4, 10, 3, 2, 5, 7, 1, g= 9 : 9, 4, 3, 5, 1, 9, 4, 3, 5, 1, g= 10 : 10, 1, 10, 1, 10, 1, 10, 1, 10, 1, edit: "pencil and paper" proof i was talking about Last fiddled with by LaurV on 2012-09-24 at 05:40
 2012-09-24, 17:22 #5 rogue     "Mark" Apr 2003 Between here and the 24·7·61 Posts I had assumed that using any discrete log algorithm should be able to solve 2^x = 5 mod 11. I'll implement the C&P version (shown by Raman above) and see if that can find the solution. If the C&P version cannot, then there must be a restriction on the inputs, a restriction not mentioned in any sources I've seen so far. If the C&P version can, then I have to assume that the wiki page is wrong.
 2012-09-24, 17:50 #6 rogue     "Mark" Apr 2003 Between here and the 24·7·61 Posts The C&P version works correctly. I'll look into where the wiki author got their information. Maybe I'll correct it or maybe someone else would be interested in fixing it.
2012-09-26, 11:20   #7
Random Poster

Dec 2008

179 Posts

Quote:
 Originally Posted by rogue If the C&P version can, then I have to assume that the wiki page is wrong.
That is a false assumption. If an algorithm relies on a random choice (in this case the iteration function), then it is very likely that any such choice has some pathological inputs for which the algorithm doesn't work. Usually this would mean that the algorithm should try other choices if one fails, but since for Pollard's rho failures are only expected when the modulus is very small (in which case trial exponentiation is a faster way to find the DL), no one ever bothers to implement it like that.

 Similar Threads Thread Thread Starter Forum Replies Last Post henryzz Math 2 2017-08-15 12:13 Joe O Factoring 9 2016-09-18 15:42 AnoNYStudent Homework Help 26 2011-12-07 00:18 fgrieu Software 22 2011-11-25 19:47 theta Factoring 2 2005-08-23 21:14

All times are UTC. The time now is 20:18.

Mon Dec 5 20:18:40 UTC 2022 up 109 days, 17:47, 0 users, load averages: 0.55, 0.83, 0.82