20070928, 14:28  #1 
3^{2}·5·167 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. 
20070928, 15:23  #2  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}·937 Posts 
Quote:
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. 

20070928, 17:32  #3 
Aug 2002
Buenos Aires, Argentina
2·733 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? 
20070928, 17:42  #4  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}×937 Posts 
Quote:
I would start by enumerating the primitive roots of 811. 

20070929, 01:45  #5 
Jun 2003
37×43 Posts 
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 20070929 at 01:46 
20070929, 02:04  #6  
7F7_{16} Posts 
Quote:
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? 

20071001, 22:12  #7 
2622_{10} Posts 
I finally figured out how to do this. The PohligHellman algorithm (http://en.wikipedia.org/wiki/PohligHellman_algorithm) allows quick determination of the discrete logarithm of a smooth integer.

20071002, 09:42  #8  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}·937 Posts 
Quote:


20071002, 10:12  #9 
Dec 2005
C4_{16} Posts 
clueless crank...are there many cranks that have a clue ?

20071002, 11:15  #10 
"Bob Silverman"
Nov 2003
North of Boston
2^{3}·937 Posts 

20071002, 20:24  #11 
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
2^{2}·11·263 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Help with discrete logarithm  pinnn  Information & Answers  43  20210318 15:40 
GDLOG discrete logarithm usage example  xkyve  Information & Answers  38  20140714 15:59 
Discrete logarithm software  Unregistered  Information & Answers  39  20120427 20:08 
Finding totient using discrete logarithm  vector  Miscellaneous Math  3  20071120 18:50 
Discrete logarithm mod Mersenne primes?  Unregistered  Information & Answers  0  20060827 15:32 