Discrete logarithms and primitive roots

A primitive root has the maximum order, so its powers visit every nonzero residue

Every public-key exchange needs a computation that is easy in one direction and, as far as anyone knows, infeasible to undo in the other. Raise a number to a power modulo a prime and the answer falls out in a handful of squarings, however large the exponent. Run the process backwards, given only the base, the modulus and the result, and there is no known shortcut. That one-way street is called the discrete logarithm problem, and Diffie-Hellman key exchange, covered in Module 6, is built directly on top of it.

For a prime $p$ and an integer $a$ not divisible by $p$, the order of $a$ modulo $p$ is the smallest positive $n$ with $a^n \equiv 1 \pmod{p}$. By Fermat’s little theorem, $a^{p-1} \equiv 1 \pmod{p}$ always holds, so the order of $a$ is at most $p - 1$. For most $a$ it is smaller, meaning the powers of $a$ cycle back to $1$ early and never touch some of the other nonzero residues.

An element whose order is exactly $p - 1$, the maximum possible, is a primitive root of $p$. Its powers $g^1, g^2, \ldots, g^{p-1}$ run through every nonzero residue modulo $p$ exactly once before returning to $1$.

Try it — worked example

Is 2 a primitive root of 19? Find its order.

Show answer and steps

Answer2 is a primitive root of 19, with order 18

The lecture demonstrates this for $p = 19$, $g = 2$, printing rows $1$ through $6$ of the table, an ellipsis, and then rows $17$ and $18$. The full sequence, computed the same way at every step (multiply the previous result by $2$ and reduce), is below.

1. $2^1 \bmod 19 = 2$
2. $2^2 \bmod 19 = 4$
3. $2^3 \bmod 19 = 8$
4. $2^4 \bmod 19 = 16$
5. $2^5 \bmod 19 = 32 \bmod 19 = 13$
6. $2^6 \bmod 19 = 26 \bmod 19 = 7$
7. $2^7 \bmod 19 = 14$
8. $2^8 \bmod 19 = 28 \bmod 19 = 9$
9. $2^9 \bmod 19 = 18$
10. $2^{10} \bmod 19 = 36 \bmod 19 = 17$
11. $2^{11} \bmod 19 = 34 \bmod 19 = 15$
12. $2^{12} \bmod 19 = 30 \bmod 19 = 11$
13. $2^{13} \bmod 19 = 22 \bmod 19 = 3$
14. $2^{14} \bmod 19 = 6$
15. $2^{15} \bmod 19 = 12$
16. $2^{16} \bmod 19 = 24 \bmod 19 = 5$
17. $2^{17} \bmod 19 = 10$
18. $2^{18} \bmod 19 = 20 \bmod 19 = 1$
19. All eighteen values are distinct, and $2^{18}$ is the first power to return to $1$. So the order of $2$ modulo $19$ is $18 = \varphi(19)$, and $2$ is a primitive root.

Pitfall

Row $5$ above is $2^5 \bmod 19 = 13$. The Week 4 supplement prints $2^5 \bmod 19 = 12$, which is wrong: $2^5 = 32$, and $32 - 19 = 13$. The source’s own next line, $2^6 \bmod 19 = 7$, is only reachable by doubling the correct $13$ (doubling $12$ gives $5$). Rows $7$ through $16$ are not printed in the source at all, and are filled in here by the same repeated-doubling computation so the order-$18$ claim can be checked in full.

Optional aside

The six primitive roots of $19$ fall out of the table above. A power $2^k$ is itself a primitive root exactly when $\gcd(k, 18) = 1$, since only then does $2^k$ generate the full cycle. The $k$ from $1$ to $18$ coprime to $18$ are $1, 5, 7, 11, 13, 17$, and there are $\varphi(18) = 6$ of them. Reading those rows off the table: $2^1 = 2$, $2^5 = 13$, $2^7 = 14$, $2^{11} = 15$, $2^{13} = 3$, $2^{17} = 10$. Sorted, that set is $\{2, 3, 10, 13, 14, 15\}$, exactly the primitive roots the lecture lists.

Exponentiation is easy and its inverse, the discrete logarithm, is not

Ordinary logarithms invert exponentiation: given $y = g^x$, $\log_g y$ recovers $x$. The discrete logarithm is the modular analogue. For a prime $p$ and a primitive root $g$ of $p$, $y = g^x \bmod p.$

Formula

Discrete logarithm problem (DLP)

$$y = g^x \bmod p$$

$p$

a prime

$g$

a primitive root of p

$x$

the discrete logarithm of y to base g

$y$

the result, given

Given g, x, p, finding y is easy. Given g, y, p, finding x is not: the DLP asks for the second direction.

The two directions have different costs.

Forward: exponentiation, easy. Given $g$, $x$ and $p$, computing $y = g^x \bmod p$ is fast: the previous page’s square-and-multiply method does it in about $\log_2 x$ modular multiplications, however large $x$ is. For $p = 19$, $g = 2$, $x = 7$: $y = 2^7 \bmod 19 = 128 \bmod 19 = 14$, matching row $7$ of the table above.

Reverse: the discrete logarithm, hard. Given $g$, $y$ and $p$, finding $x$ has no known method faster than something close to exhaustive search over every possible exponent. For $p = 19$, $g = 2$, $y = 8$: solving $8 = 2^x \bmod 19$ means scanning the table until $2^x$ lands on $8$. Row $3$ gives $2^3 \bmod 19 = 8$, so $x = 3$. That search only finishes at a glance because $p = 19$ is small enough to hold the whole table in view. For a prime with hundreds of digits the search space is far too large to scan, and no faster general algorithm is known.

Exam detail

“No known faster algorithm” is a computational hardness assumption, not a proof. Nobody has proven the discrete logarithm problem hard; the best known general attacks (index calculus and its relatives) are still exponential or sub-exponential in the size of $p$, and every cryptosystem built on the DLP is only as secure as that gap holding up. RSA’s hardness assumption has the same status, and the exam draws the same distinction for both: believed hard, not proven hard.

That asymmetry is what Diffie-Hellman builds on

Cheap to compute forward and expensive to invert is precisely what a public-key exchange needs. Diffie-Hellman key exchange, covered in Diffie-Hellman key exchange, has each party publish $g^a \bmod p$ and $g^b \bmod p$ over an open channel while keeping $a$ and $b$ private. Anyone listening sees $g$, $p$, and both public values, and reconstructing either private exponent from those is exactly the discrete logarithm problem. Public-key cryptography and trapdoor functions covers where this fits alongside the RSA problem as one of the two hardness assumptions Module 6 is built on.

Recall

Why does knowing the discrete logarithm problem is hard tell you nothing about how hard it is to compute g^x mod p in the forward direction?

They are different computations with different costs. Forward exponentiation has an efficient algorithm (square-and-multiply) regardless of how large $x$ is. The discrete logarithm problem is about the absence of an efficient algorithm for the reverse direction: recovering $x$ from $g$, $y$ and $p$. A problem can be trivially easy one way and believed infeasible the other way at the same time; that gap is the entire point.