How to find $k$ in $6^{k} \equiv 2 \mod {13}$

Question

Find for which $k$ is $6^{k} \equiv 2 \mod {13}$

I'm having trouble with these types of question in my cryptography class. This is part of Diffie–Hellman algorithm for calculating a shared key.

I know that this can be written as discrete logarithm $\log_{6}{k}$ in $Z^{*}_{13}$ but that is all I could manage to do.

Thanks for any help.

Answer 1

Trial and error, since the modulus is small.

If the modulus is larger then the problem is believed to be computationally difficult - this is the whole point of Diffie-Hellman!

Answer 2

(New to this, someone probably has a better solution, you should wait before accepting)

By Fermat's little theorem, $$6^{12}\equiv1\pmod{13}$$

Therefore the powers of $6$ modulo 13 must cycle in sets of at most $12$.

Now, we just check by hand and get

$$6^5\equiv2\pmod{13}$$

Thus $k=12t+5$ for all $t\in\Bbb Z$

Because,

$$6^{12t+c}\equiv 6^c\left(6^{12}\right)^t\equiv 6^c \pmod{13}$$

Answer 3

As $\displaystyle2^4=3\pmod{13}, 2=6^k=2^k\cdot3^k=2^k\cdot(2^4)^k=2^{5k}$

$\implies 2^{5k}\equiv2\iff2^{5k-1}\equiv1$

Now, $2^6=64\equiv-1\pmod{13}\implies$ord$_{13}2=12$ which must divide $5k-1$

$\displaystyle\implies5k\equiv1\pmod{12}\equiv1+24\iff k\equiv5\pmod{12}$ as $(5,12)=1$

Answer 4

You can also try dividing by $6$ noting that $6\times -2=-12\equiv 1$ mod $13$, so that dividing by $6$ is equivalent to multiplying by $-2$ so

$6^{k}\equiv 2$

$6^{k-1}\equiv -4$

$6^{k-2}\equiv 8$

$6^{k-3}\equiv -16\equiv -3$

$6^{k-4}\equiv 6$

$6^{k-5}\equiv -12\equiv 1$

Hence $k=5$ will do. Of course this trick to simplify the arithmetic is not always available.