Discrete logarithms and primitive roots

The order of an element modulo a prime, the primitive-root condition, the discrete logarithm problem, and why one direction is easy while the other is believed hard.

Define the order of an element modulo p and state the condition that makes it a primitive root.
Verify that 2 is a primitive root of 19 by computing its full sequence of powers.
State the discrete logarithm problem and identify which direction is easy and which is hard.
Explain why that asymmetry is what Diffie-Hellman key exchange relies on.

16 min read

Intuition

Every public-key exchange needs a computation that is easy to do in one direction and, as far as anyone knows, infeasible to undo in the other. Multiplication and factoring are one such pair for RSA; exponentiation and its inverse are the pair here. Raise a number to a power modulo a prime, and the answer falls out in a handful of squarings, however large the exponent (the previous page covers exactly that). Run the process backwards, given only the base, the modulus and the result, and there is no known shortcut: an attacker is reduced to something close to trying values one at a time. 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.

Mechanism

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 guaranteed to be at most $p - 1$ . For most $a$ , though, it is smaller than that, 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$ .

Worked example

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.

$2^1 \bmod 19 = 2$
$2^2 \bmod 19 = 4$
$2^3 \bmod 19 = 8$
$2^4 \bmod 19 = 16$
$2^5 \bmod 19 = 32 \bmod 19 = 13$
$2^6 \bmod 19 = 26 \bmod 19 = 7$
$2^7 \bmod 19 = 14$
$2^8 \bmod 19 = 28 \bmod 19 = 9$
$2^9 \bmod 19 = 18$
$2^{10} \bmod 19 = 36 \bmod 19 = 17$
$2^{11} \bmod 19 = 34 \bmod 19 = 15$
$2^{12} \bmod 19 = 30 \bmod 19 = 11$
$2^{13} \bmod 19 = 22 \bmod 19 = 3$
$2^{14} \bmod 19 = 6$
$2^{15} \bmod 19 = 12$
$2^{16} \bmod 19 = 24 \bmod 19 = 5$
$2^{17} \bmod 19 = 10$
$2^{18} \bmod 19 = 20 \bmod 19 = 1$
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 this row as $2^5 \bmod 19 = 12$ , which is wrong: $2^5 = 32$ , and $32 - 19 = 13$ , not $12$ . This is a source arithmetic slip, not a different convention. Every other explicitly printed row (rows $1$ to $4$ , $6$ , $17$ , $18$ ) matches the computation above exactly, and the source’s own next line, $2^6 \bmod 19 = 7$ , is only reachable by doubling the correct $13$ , not the printed $12$ (doubling $12$ gives $24 \bmod 19 = 5$ , not $7$ ). Rows $7$ through $16$ are not printed in the source at all: it shows the first six rows, an ellipsis, then jumps to rows $17$ and $18$ . They are filled in here by the same repeated-doubling computation so the order- $18$ claim can be checked in full.

Aside

The six primitive roots of $19$ are not a separate fact to memorise: they 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 rather than a shorter one. The values of $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.

Mechanism

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.

Mechanism

Two directions, two 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, regardless of how 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$ for $x$ 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 here because $p = 19$ is small enough to hold the whole table in view. The lecture’s point survives the toy scale: for a prime with hundreds of digits, the equivalent search space is far too large to scan, and no faster general algorithm is known.

Exam detail

“No known faster algorithm” is doing real work in that last sentence: it is a computational hardness assumption, not a proof. Nobody has proven the discrete logarithm problem is hard in the way $P \neq NP$ would make precise; 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. This is the same status RSA’s hardness assumption has, and the exam draws the same distinction for both: believed hard, not proven hard.

Mechanism

This asymmetry, 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.

Source

Week 4 Number Theory PDF