In the last lesson, every nonzero element of $\mathrm{GF}(8)$ was a power of $x$. That is no accident: the multiplicative group of every finite field is cyclic. This is the fact behind discrete-logarithm cryptography and the log tables used to multiply in hardware.
Why it works
Proof. For each $d \mid q - 1$ let $\psi(d)$ be the number of elements of order $d$ in $F^{*}$. If some $a$ has order $d$, then $1, a, \dots, a^{d-1}$ are $d$ different roots of $x^{d} - 1$, which has at most $d$ roots in a field; so the elements of order $d$ all lie in $\langle a \rangle$, a cyclic group with exactly $\varphi(d)$ of them. Hence $\psi(d)$ is $0$ or $\varphi(d)$. Now $\sum_{d} \psi(d) = q - 1 = \sum_{d} \varphi(d)$ (every element has some order; and the divisor sum of $\varphi$), so every $\psi(d) = \varphi(d)$. In particular $\psi(q - 1) = \varphi(q - 1) \ge 1$: there is an element of order $q - 1$. $\square$
A generator of $F^{*}$ is a primitive element; there are $\varphi(q - 1)$ of them. Two more facts: $\mathrm{GF}(p^{n})$ contains a subfield $\mathrm{GF}(p^{m})$ exactly when $m \mid n$ (for one direction, if $K \subseteq \mathrm{GF}(p^{n})$ has $p^{m}$ elements, the tower law over $\mathbb{Z}_{p}$ gives $m \mid n$); and then that subfield is unique.
Worked example: Is $x$ primitive?
- $x^{5} - 1 = (x - 1)(x^{4} + x^{3} + x^{2} + x + 1)$, so $x^{5} = 1$ in this field.
- $5$ is prime and $x \ne 1$, so the order of $x$ is $5$, not $15$.
Answer: Order $5$: here $x$ is not primitive, though the quotient is still the field $\mathrm{GF}(16)$.
Worked example: Counting and subfields
- $F^{*}$ is cyclic of order $63$: $\varphi(63) = \varphi(9)\varphi(7) = 6 \cdot 6 = 36$ primitive elements.
- $64 = 2^{6}$; the divisors of $6$ are $1, 2, 3, 6$, giving subfields of sizes $2, 4, 8, 64$.
Answer: $36$ primitive elements; subfields $\mathrm{GF}(2)$, $\mathrm{GF}(4)$, $\mathrm{GF}(8)$, $\mathrm{GF}(64)$.
Common mistake
Key idea