mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2007-09-28, 14:28   #1
Coffenator
 

176016 Posts
Question 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.
  Reply With Quote
Old 2007-09-28, 15:23   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by Coffenator View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2007-09-28, 17:32   #3
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

5×269 Posts
Default

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?
alpertron is offline   Reply With Quote
Old 2007-09-28, 17:42   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by alpertron View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2007-09-29, 01:45   #5
Citrix
 
Citrix's Avatar
 
Jun 2003

157910 Posts
Default

Quote:
Originally Posted by Coffenator View Post
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
Citrix is offline   Reply With Quote
Old 2007-09-29, 02:04   #6
Unregistered
 

4,271 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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?
  Reply With Quote
Old 2007-10-01, 22:12   #7
Coffenator
 

32×5×132 Posts
Smile

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.
  Reply With Quote
Old 2007-10-02, 09:42   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by Unregistered View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2007-10-02, 10:12   #9
Kees
 
Kees's Avatar
 
Dec 2005

22×72 Posts
Default

clueless crank...are there many cranks that have a clue ?

Kees is offline   Reply With Quote
Old 2007-10-02, 11:15   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by Kees View Post
clueless crank...are there many cranks that have a clue ?

Sure. Jack Sarfatti, for one.
R.D. Silverman is offline   Reply With Quote
Old 2007-10-02, 20:24   #11
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

24×5×7×19 Posts
Default

Quote:
Originally Posted by Kees View Post
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
xilman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Help with discrete logarithm pinnn Information & Answers 43 2021-03-18 15:40
GDLOG discrete logarithm usage example xkyve Information & Answers 38 2014-07-14 15:59
Discrete logarithm software Unregistered Information & Answers 39 2012-04-27 20:08
Finding totient using discrete logarithm vector Miscellaneous Math 3 2007-11-20 18:50
Discrete logarithm mod Mersenne primes? 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.