Thread: Discrete Log Problem

Good morning, I had trouble with this:

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

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

Thank you...

Originally Posted by cryptocrow

Good morning, I had trouble with this:

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

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

Thank you...

$\displaystyle 3^{10} = 2 \text{ \, mod \, 137}$

$\displaystyle 3^{20} = 4 \text{ \, mod \, 137}$

$\displaystyle 3^{-20} = 4^{-1} \text{ \, mod\, 137}$

$\displaystyle 3^6 = 44 \text{ \, mod \, 137} \Rightarrow (3^6)(3^{-20}) = (44)(4^{-1}) \text{ \, mod\, 137}$

$\displaystyle 3^{-14} = 11 \text{ \,mod \, 137}$

By Fermats little theorem $\displaystyle 3^{136} = 1 \text{ \, mod \, 137}$

$\displaystyle 3^{122} = 11 \text{ \, mod\, 137}$

So $\displaystyle x = 122$

Ah, I see where I went wrong... thanks for your help!