Discrete logarithm problem: does the base have to be a generator of Z? $\mathbb{Z}_p$ under multiplication, p=13, Z={1,…12}
I need to find the discrete logarithm of base 5 to 8:
So essentially $5^x \equiv 8 \pmod{13}$
From what I read the base must be a generator of $\mathbb{Z}_p$ -> (https://www.doc.ic.ac.uk/~mrh/330tutor/ch06s02.html)
However, In this problem 5 is not a generator of $\mathbb{Z}_{13}$. 5 produces a cyclical group {5,12,8,1} which does not contain all the elements of $\mathbb{Z}_{13}$.
I understand there is a solution to this, but can someone clarify this rule for me?
 A: Let us first clear up a notational confusion.  Let $\mathbb{Z}_{13} = \mathbb{Z} / 13 \mathbb{Z}$ be the "ring of integers modulo thirteen".  That is, we add, subtract, and multiply as usual in $\mathbb{Z}$, however we are allowed to discard multiples of $13$ whenever we like. For example, we have:
$$
2 \cdot 7 = 14 = 1\, (\mathrm{mod}\, 13)
$$
We use $\mathbb{Z}_{13}^\times$ to denote the multiplicative structure of $\mathbb{Z}_{13}$.  That is, we remove zero, and disallow addition and subtraction.  This works nicely because $13$ is prime.  In fact, $\mathbb{Z}_{13}^\times$ under multiplication forms a cyclic commutative group with identity equal to $1$.  This needs a proof, of course!
In general, the discrete logarithm problem asks the following:

Given $a, b, n$ positive integers, find all solutions (if any exist) to the equation $a^x = b\, (\mathrm{mod}\, n)$.

As your example shows, even when $n$ is prime and $a$ does not generate $\mathbb{Z}_{p}^\times$, it is possible for there to be solutions to the discrete logarithm problem.
