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

 2007-09-28, 14:28 #1 Coffenator   3·13·97 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

"Bob Silverman"
Nov 2003
North of Boston

23·3·311 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 2×727 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

"Bob Silverman"
Nov 2003
North of Boston

23×3×311 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

30648 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

53×113 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   22·3·17·23 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

"Bob Silverman"
Nov 2003
North of Boston

23×3×311 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

"Bob Silverman"
Nov 2003
North of Boston

11101001010002 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

2C9E16 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 23:40.

Mon Aug 8 23:40:51 UTC 2022 up 32 days, 18:28, 1 user, load averages: 1.67, 1.75, 1.62