Understanding powers of an element

Question

For example we have:

$$ \begin{aligned} \mathbb{Z}_7^* &= \left\{[z]_7 \in \mathbb{Z}_7 : \gcd(z, 7) = 1, 1 \leq z < 7, \forall z \in \mathbb{Z}\right\} \\ &= \{1, 2, 3, 4, 5, 6\} \\ \left<a\right> &\in \mathbb{Z}_7^* : \{a^b \mod 7: \forall a,b \in \mathbb{Z}_7^*\} \end{aligned} $$

This would produce:

$$ \begin{aligned} \left<1\right> &= \{1\} \\ \left<2\right> &= \{1,2,4\} \\ \left<3\right> &= \{1,2,3,4,5,6\} \\ \left<4\right> &= \{1,2,4\} \\ \left<5\right> &= \{1,2,3,4,5,6\} \\ \left<1\right> &= \{1,6\} \end{aligned} $$

As such, the smallest primitive root $g = 3$ as $\left<3\right> = |\mathbb{Z}_7^*|$.

So, $g$ is our generator, that can construct $\mathbb{Z}_7^*$ and the element of $a \in \mathbb{Z}_7^*$ can be expressed as:

$$ 3^z \equiv a \pmod7 \to z = \text{ind}_{7,3}(a) $$

Now, my issue, how do I solve for $z$ given $a$:

Lets say $a = 4$ we want to solve:

$$ 3^z \equiv 4 \pmod7 \to 3^z \mod 7 = 4 \mod7 = 4 $$

I think I understand this correctly, I just do not know how to solve for $z$.

Now this relates to a question I need to answer, just with different numbers. Both of which are $\mathbb{Z}_p^*$ where $p$ is a prime number, not sure if that is significant or not.

Draw the table order of $\mathbb{Z}_7^*$ choose the smallest $g$ and compute a table giving $\text{ind}_{7, g}(a) \forall a \in \mathbb{Z}_7^*$.

Now I believe I did the first part correct, the $\left<a\right>$ is the order table and $g = 3$.

Answer 1

This is the discrete logarithm problem, and we don't know a general-purpose efficient algorithm for solving it. However, you can figure out the answer by building up a table of answers for different values of the exponent $x$.

$$3^x = 4\pmod{7}$$

The powers of 3 (mod 7) are, in order: $3^0 \equiv 1,\;\;3^1 \equiv 3,\;\; 3^2 \equiv 2,\;\; 3^3 \equiv 6,\;\; 3^4 \equiv 4,\;\; 3^5 \equiv 5,\;\; 3^6 \equiv 1,$ and the cycle repeats for all higher powers.

Hence:

$$\begin{array}{r|rrrrrr}x&0&1&2&3&4&5&\cr 3^x\pmod{4}&1&3&2&6&4&5\cr\end{array} $$

And more generally,

$$\begin{array}{r|rrrrrr}3^x\pmod{4}&1&3&2&6&4&5\\\hline x&0&1&2&3&4&5&\\&6&7&8&9&10&11\\&12&13&14&15&16&17\\&18&19&20&21&22&23\\&&&\vdots&\vdots&& \end{array} $$

Answer 2

Let $g$ be a fixed number and $p$ a fixed modulus. Computationally, "given $z$, find $g^z$" is (relatively) easy; "given $g^z$, find $z$" is hard.

So, construct your table "backwards". For example, if $p=7$ and $g=3$, don't do $$\matrix{\hbox{number}&1&2&3&4&5&6\cr \hbox{index}&?&?&?&?&?&?\cr}$$ but rather $$\matrix{\hbox{number}&?&?&?&?&?&?\cr \hbox{index}&0&1&2&3&4&5\cr}\ .$$ Then all you have to calculate is $$3^0=1\,,\ 3^1=3\,,\ 3^2=9=2\,,\ 3^3=2\times3=6\,,\ldots$$ to get $$\matrix{\hbox{number}&1&3&2&6&4&5\cr \hbox{index}&0&1&2&3&4&5\cr}\ .$$ Finally (optional) sort the table so that the top row is in numerical order.