With a primitive root $g$ mod $p$, every nonzero residue is a power of $g$. The exponent that produces it plays the role of a logarithm, and it obeys the familiar logarithm rules, with one twist about where it lives.
Definition. Let $g$ be a primitive root mod a prime $p$, and $p \nmid h$. The discrete logarithm of $h$ to base $g$, written $\log_g h$ (also called the index of $h$), is the unique $k$ with $0 \le k \le p - 2$ and $$g^{k} \equiv h \pmod{p}.$$ Any $k' \equiv k \pmod{p - 1}$ also works, since $g^{p-1} \equiv 1$.
Rules. Mod $p - 1$: $\ \log_g(ab) \equiv \log_g a + \log_g b$ and $\log_g(a^{m}) \equiv m \log_g a$.
💡 Why it works
If $g^{s} \equiv a$ and $g^{t} \equiv b$, then $g^{s + t} = g^{s} g^{t} \equiv ab$, so $s + t$ is a logarithm of $ab$. Exponents of $g$ only matter mod $p - 1$, the order of $g$ (as in orders), so the logarithm is $s + t$ reduced mod $p - 1$. The same argument gives the power rule.
Finding a discrete logarithm by brute force: list the powers until $h$ appears. Checking an answer takes one fast power; finding it took a search.
From the list, $2^{4} \equiv 5$, so $\log_2 5 = 4$.
All solutions: $x \equiv 4 \pmod{10}$, that is $x = 4, 14, 24, \dots$ (and $-6, -16, \dots$).
Answer: $x \equiv 4 \pmod{10}$.
A table of discrete logarithms mod 11, base 2. Like an old table of logarithms, it turns multiplication into addition: $4 \cdot 6 = 24 \equiv 2$, and $2 + 9 = 11 \equiv 1$, the log of 2.
$h$
1
2
3
4
5
6
7
8
9
10
$\log_2 h \bmod 11$
0
1
8
2
4
9
7
3
6
5
⚠️ Common mistake
Reducing a discrete logarithm mod $p$ instead of mod $p - 1$. In the second example, "$15 \equiv 4 \pmod{11}$" would claim $2^{4} \equiv 10$, but $2^{4} \equiv 5$. Logarithms are exponents, and exponents of $g$ cycle with period $p - 1$.
Computing $g^{k} \bmod p$ is fast. Going backward, from $h$ to $k$, has no known fast method on ordinary (non-quantum) computers for a general large prime $p$: the best algorithms still take time that grows faster than any power of the number of digits. This one-way behavior is what Diffie–Hellman relies on.
🔑 Key idea
$\log_g h$ is the exponent $k$ with $g^{k} \equiv h \pmod{p}$. It lives mod $p - 1$; logarithms of products add mod $p - 1$.
Practice
Pass with 3 right answers, the last 2 in a row. Each right answer earns 3 XP.
William Stein, Elementary Number Theory: Primes, Congruences, and Secrets (Springer, 2009; free online edition), chapter 2, The Ring of Integers Modulo n, and chapter 3, Public-Key Cryptography
MIT OpenCourseWare 18.781 Theory of Numbers (Spring 2012), lecture notes on primitive roots and indices