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.

[R.D. Silverman]

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.

[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?

[R.D. Silverman]

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.

[Citrix]

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.

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?

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.

[R.D. Silverman]

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.

[Kees]

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

[R.D. Silverman]

Originally Posted by Kees

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

Sure. Jack Sarfatti, for one.

[xilman]

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