I'm trying to teach myself Cryptography and came across some old exam questions which include questions about the discrete logarithm, I'm just wondering if it's as straight forward as I'm thinking it is:
$ p=37, \space g=3 $
(a) Explain how to solve $ 27= g^x\space mod \space p $ for x without using brute force.
(b) Make a table of $ g^n\space mod \space p \space for \space n =1...18.$
(c) Is g a generator for $ Z^×_{37}? $ Say why.
(d) Using the table above, $ 4= g^y \space mod \space p \space for \space y $ by brute force.
If anyone can shed a bit of light on these it would be really appreciated.
(a) Explain how to solve $ 27= g^x\space mod \space p $ for x without using brute force.
In the given case You can apply logarithm $x = \log_327=3$
For more complicated cases you cann use Baby-step Giant-step for example :
$$3^x \equiv 27 (\text{ mod } 37)$$ $\varphi(37) = 36$
$m = \lceil \sqrt{36} \rceil = 6$
$\begin{array}{c|ccccc} j& 0 & 1 & 2 & 3 & 4 & 5 \\ \hline 3^j & 1 & 3& 9 & \color{#f00}{27} & 7 & 21 \end{array}$
$3^{-6}= 3^{36 -6 } = 3^{30} \text{ mod }37 = 10$
$\begin{array}{c|ccccc} i & 0 \\ \hline 27\cdot 10^i & \color{#f00}{27} \end{array}$
Also... $$x = i\cdot m + j = 0\cdot 6 + 3 = 3 $$ $$3^{3} \equiv 27 (\text{ mod } 37)$$
(b) Make a table of $ g^n\space mod \space p \space for \space n =1...18.$
$\begin{array}{c|ccccc} j& 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18\\ \hline 3^j & 1 & 3& 9 & 27 & 7 & 21 & 26 & 4 & 12 &36 & 34 & 29 & 10 & 30 & 16 & 11 & 33 & 25 & 1 \end{array}$
(c) Is g a generator for $ Z^×_{37}? $ Say why.
(shown the Comment from Ethan Bolker).
(d) Using the table above, $ 4= g^y \space mod \space p \space for \space y $ by brute force.
$\begin{array}{c|ccccc} j& 0 & 1 & 2 & 3 & 4 & 5 \\ \hline 3^j & 1 & \color{#f00}{3}& 9 & 27 & 7 & 21 \end{array}$
$\begin{array}{c|ccccc} i & 0 & 1 \\ \hline 4\cdot 10^i & 4 & \color{#f00}{3} \end{array}$
Also... $$x = i\cdot m + j = 1\cdot 6 + 1 = 7 $$ $$3^{7} \equiv 4 (\text{ mod } 37)$$
I hope I was of help