mersenneforum.org  

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

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

3·13·97 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
 
"Bob Silverman"
Nov 2003
North of Boston

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

2×727 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
 
"Bob Silverman"
Nov 2003
North of Boston

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

30648 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
 

53×113 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
 

22·3·17·23 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
 
"Bob Silverman"
Nov 2003
North of Boston

23×3×311 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
 
"Bob Silverman"
Nov 2003
North of Boston

11101001010002 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

2C9E16 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 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

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.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”