20120923, 13:43  #1 
"Mark"
Apr 2003
Between here and the
2^{4}×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?

20120923, 16:10  #2 
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 x_{i} = t^{a[SUB]i[/SUB]}g^{b[SUB]i [/SUB]}(mod p) and a_{0} = 0, b_{0} = 0, x_{0} = 1. Here, we define a pseudo random function such as:
(a_{i+1}, b_{i+1}) = (a_{i + 1} (mod φ(p)), b_{i}), if 0 < x_{i} < p/3 (a_{i+1}, b_{i+1}) = (2a_{i} (mod φ(p)), 2b_{i} (mod φ(p))), if p/3 < x_{i} < 2p/3 (a_{i+1}, b_{i+1}) = (a_{i}, b_{i + 1} (mod φ(p))), if 2p/3 < x_{i }< p And so, we have that x_{i+1} = t^{x[SUB]i[/SUB]} (mod p), if 0 < x_{i} < p/3 x_{i+1} = x_{i}^{2} (mod p), if p/3 < x_{i} < 2p/3 x_{i+1} = g^{x[SUB]i[/SUB]} (mod p), if 2p/3 < x_{i} < p We compare the different values of x_{i }to find out a match. Similar to the tortoisehare algorithm (Floyd’s cycle finding algorithm), we compare x_{1} with x_{2}, x_{2} with x_{4}, x_{3} with x_{6} and so on. We compare x_{m} with x_{2m} 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 x_{j} = x_{k}, then we have t^{a[SUB]j[/SUB]}g^{b[SUB]j[/SUB]} = t^{a[SUB]k[/SUB]}g^{b[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 = g^{l}, we will have (a_{j} – a_{k}).l ≡ b_{k} – b_{j} (mod φ(p)), from which we could calculate the value of l as to be l = (b_{k} – b_{j})(a_{j} – a_{k})1 (mod φ(p)). Last fiddled with by Raman on 20120923 at 16:22 
20120923, 17:56  #3 
"Mark"
Apr 2003
Between here and the
1AB0_{16} 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.

20120924, 05:36  #4 
Romulan Interpreter
"name field"
Jun 2011
Thailand
24006_{8} 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, Last fiddled with by LaurV on 20120924 at 05:40 
20120924, 17:22  #5 
"Mark"
Apr 2003
Between here and the
2^{4}·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.

20120924, 17:50  #6 
"Mark"
Apr 2003
Between here and the
2^{4}·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. 
20120926, 11:20  #7 
Dec 2008
179 Posts 
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.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Pollard rho with known factor of P1  henryzz  Math  2  20170815 12:13 
Pollard rho questions  Joe O  Factoring  9  20160918 15:42 
Parallelizing Pollard's P1 Algorithm  AnoNYStudent  Homework Help  26  20111207 00:18 
Efficiency of stateoftheart Pollard's p1  fgrieu  Software  22  20111125 19:47 
Pollard Rho Help?  theta  Factoring  2  20050823 21:14 