1. ## Discrete Logarithms

Given that:

3^6 = 44 (mod 137)
3^10 = 2 (mod 137)

find x such that 3^x = 11 (mod 137)
such that 0 < x < 135

My attempt:
I first noticed that fact that 11 = (44/2)/2
So I tried using that.
I though maybe I can subtract the exponents and test my luck.
(3^6)/(3^10) = (3^-4)
(3^-4)/(3^10) = (3^-14)
-14 + 137 = 123

Doesn't work out. And Im sure there are a few things wrong with this.
Ive been looking at this question for quite some time. So now I am here for advice.

The answer I am looking for is 122.

From looking at an ElGamal Cryptosystem example (http://www14.informatik.tu-muenchen....yptosystem.pdf)
There is a statement that says 15^-5 (mod 17) = 15 ^11 (mod 17) = 9

Is it just a coincidence that -5 + 17 = 12 (1 more than 11) and -14 + 137 = 123 (1 more than 122)?
What is the proper way to solve modular arithmetic with a negative exponent?

3. Originally Posted by chrisc
There is a statement that says 15^-5 (mod 17) = 15 ^11 (mod 17) = 9
By Fermat's Little Theorem is $\displaystyle m \equiv n ~\text{(mod p - 1)}$ then $\displaystyle a^m \equiv a^n~\text{(mod p)}$. In this case $\displaystyle -5 \equiv 11 ~\text{(mod 16)}$ thus $\displaystyle 15^{-5} \equiv 15^{11} ~\text{(mod 17)}$.

I'm working on your original problem, but don't expect results. I'm not catching on how to look at it.

-Dan

4. Originally Posted by chrisc
What is the proper way to solve modular arithmetic with a negative exponent?
5^(-15) = 1/3^(15). Since this is a fraction and no fractions can be allowed in modular math, we need to prove that the inverse exists.

-Dan

5. Originally Posted by chrisc
Given that:

3^6 = 44 (mod 137)
3^10 = 2 (mod 137)

find x such that 3^x = 11 (mod 137)
such that 0 < x < 135

My attempt:
I first noticed that fact that 11 = (44/2)/2
So I tried using that.
I though maybe I can subtract the exponents and test my luck.
(3^6)/(3^10) = (3^-4)
(3^-4)/(3^10) = (3^-14)
-14 + 137 = 123

Doesn't work out. And Im sure there are a few things wrong with this.
Ive been looking at this question for quite some time. So now I am here for advice.

The answer I am looking for is 122.
Got it. Remember Fermat's Little Theorem? We're doing the reverse: (This is all mod 137, a prime.)
$\displaystyle 2 \cdot 2 \cdot 11 = 44$

$\displaystyle 3^{10} \cdot 3^{10} \cdot 3^x = 44 = 3^6$

$\displaystyle 3^{20 + x} = 3^6$

This is all mod 137. But the reverse of Fermat's Little says that if $\displaystyle a^m \equiv a^n ~\text{(mod p)}$ then $\displaystyle m \equiv n ~\text{(mod p-1)}$.

Thus since $\displaystyle 3^{20 + x} \equiv 3^6 ~\text{(mod 137)}$ implies that $\displaystyle 20 + x \equiv 6 ~\text{(mod 136)}$. Thus x = 122.

-Dan

6. well that does solve the problem, no?

since -14 = 122 (mod 136)

*just saw your new post. ill check it out