Discrete logarithm problem: does the base have to be a generator of Z?

Question

$\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?

Answer 1

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.