mersenneforum.org Solving discrete logarithm in 2 variables
 Register FAQ Search Today's Posts Mark Forums Read

 2007-09-28, 14:28 #1 Coffenator   176016 Posts Solving discrete logarithm in 2 variables Is solving a 2 variable discrete logarithm problem just as hard as the one variable variant. By 2 variable discrete logarithm I mean solving this: 2^y = 18 mod n and 2^x = 22 mod n for x and y when n can be varied to any (preferably small) integer.
2007-09-28, 15:23   #2
R.D. Silverman

Nov 2003

746010 Posts

Quote:
 Originally Posted by Coffenator Is solving a 2 variable discrete logarithm problem just as hard as the one variable variant. By 2 variable discrete logarithm I mean solving this: 2^y = 18 mod n and 2^x = 22 mod n for x and y when n can be varied to any (preferably small) integer.
This makes zero sense. Either n is given, or it is not.
If n is given, then you simply have two separate congruences in one
variable each.

If n is NOT given, then you have two simultaneous congruences in THREE
variables.

In neither case is it a 2 variable problem.

 2007-09-28, 17:32 #3 alpertron     Aug 2002 Buenos Aires, Argentina 5×269 Posts A more interesting question would be: How do you solve for (x,y) the equations: x^y = 54 (mod 811) y^x = 141 (mod 811) without brute force?
2007-09-28, 17:42   #4
R.D. Silverman

Nov 2003

746010 Posts

Quote:
 Originally Posted by alpertron A more interesting question would be: How do you solve for (x,y) the equations: x^y = 54 (mod 811) y^x = 141 (mod 811) without brute force?
An interesting question. By "brute force", do you mean trying all (x,y)?
I would start by enumerating the primitive roots of 811.

2007-09-29, 01:45   #5
Citrix

Jun 2003

157910 Posts

Quote:
 Originally Posted by Coffenator Is solving a 2 variable discrete logarithm problem just as hard as the one variable variant. By 2 variable discrete logarithm I mean solving this: 2^y = 18 mod n and 2^x = 22 mod n for x and y when n can be varied to any (preferably small) integer.
Yes it is. Though there are some steps that can be combined. The running time for 2 problems will be sqrt(2*n) whereas for a single problem will be sqrt(n). So if we do not use the common steps then the time for 2 problems will be 2*sqrt(n). Thus doing 2 problems is 1.4 times faster.

Last fiddled with by Citrix on 2007-09-29 at 01:46

2007-09-29, 02:04   #6
Unregistered

4,271 Posts

Quote:
 Originally Posted by R.D. Silverman This makes zero sense. Either n is given, or it is not. If n is given, then you simply have two separate congruences in one variable each. If n is NOT given, then you have two simultaneous congruences in THREE variables. In neither case is it a 2 variable problem.
Actually this is 2 - 2 variable problems since the only relationship x and y have to each other is that they are not equal. The numbers 18 and 22 limit what the M can be.

I was just wondering if it was possible to pick an M so that solving both of these equations would be arbitrarily easy. Is there some property of mod powers of 2 or something that would solve both equations quickly?

 2007-10-01, 22:12 #7 Coffenator   32×5×132 Posts I finally figured out how to do this. The Pohlig-Hellman algorithm (http://en.wikipedia.org/wiki/Pohlig-Hellman_algorithm) allows quick determination of the discrete logarithm of a smooth integer.
2007-10-02, 09:42   #8
R.D. Silverman

Nov 2003

11101001001002 Posts

Quote:
 Originally Posted by Unregistered Actually this is 2 - 2 variable problems since the only relationship x and y have to each other is that they are not equal. The numbers 18 and 22 limit what the M can be. I was just wondering if it was possible to pick an M so that solving both of these equations would be arbitrarily easy. Is there some property of mod powers of 2 or something that would solve both equations quickly?
Just what we need. Another clueless crank.

 2007-10-02, 10:12 #9 Kees     Dec 2005 22×72 Posts clueless crank...are there many cranks that have a clue ?
2007-10-02, 11:15   #10
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by Kees clueless crank...are there many cranks that have a clue ?
Sure. Jack Sarfatti, for one.

2007-10-02, 20:24   #11
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

24×5×7×19 Posts

Quote:
 Originally Posted by Kees clueless crank...are there many cranks that have a clue ?
Many cranks have a clue. Very often they are clueful in fields in which they are not cranks.

The phrase "differently clued" is not purely political correctness.

Paul

 Similar Threads Thread Thread Starter Forum Replies Last Post pinnn Information & Answers 43 2021-03-18 15:40 xkyve Information & Answers 38 2014-07-14 15:59 Unregistered Information & Answers 39 2012-04-27 20:08 vector Miscellaneous Math 3 2007-11-20 18:50 Unregistered Information & Answers 0 2006-08-27 15:32

All times are UTC. The time now is 07:13.

Mon Apr 12 07:13:15 UTC 2021 up 4 days, 1:54, 1 user, load averages: 2.48, 2.26, 2.02