mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2012-09-23, 13:43   #1
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

24×7×61 Posts
Default 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?
rogue is online now   Reply With Quote
Old 2012-09-23, 16:10   #2
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3·419 Posts
Default 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
Raman is offline   Reply With Quote
Old 2012-09-23, 17:56   #3
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

1AB016 Posts
Default

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.
rogue is online now   Reply With Quote
Old 2012-09-24, 05:36   #4
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

240068 Posts
Default

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
Click image for larger version

Name:	9-24-2012 12-29-41.jpg
Views:	413
Size:	98.7 KB
ID:	8647

Last fiddled with by LaurV on 2012-09-24 at 05:40
LaurV is offline   Reply With Quote
Old 2012-09-24, 17:22   #5
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

24·7·61 Posts
Default

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.
rogue is online now   Reply With Quote
Old 2012-09-24, 17:50   #6
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

24·7·61 Posts
Default

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.
rogue is online now   Reply With Quote
Old 2012-09-26, 11:20   #7
Random Poster
 
Random Poster's Avatar
 
Dec 2008

179 Posts
Default

Quote:
Originally Posted by rogue View Post
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.
Random Poster is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Pollard rho with known factor of P-1 henryzz Math 2 2017-08-15 12:13
Pollard rho questions Joe O Factoring 9 2016-09-18 15:42
Parallelizing Pollard's P-1 Algorithm AnoNYStudent Homework Help 26 2011-12-07 00:18
Efficiency of state-of-the-art Pollard's p-1 fgrieu Software 22 2011-11-25 19:47
Pollard Rho Help? 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔