Multiplicative group in finite fields

In this lesson we shall prove the following theorem and study its consequences.

In other words, the theorem says that there exists an element $a \in \mathbb F_{p^k}^*$ such that any non-zero element of $\mathbb F_{p^k}$ can be expressed as its power $a^n$ for some integer $n$.

Let us consider the set of invertible elements $\mathbb{F}_8^*$ when the field is specified by the polynomial $\alpha^3+\alpha+ 1$. Recall that the order of any element must divide the group order. As there are $7$ elements in $\mathbb{F}_8^*$, the order of any element must be either $1$ or $7$. For instance, \[\begin{align*} &\begin{aligned} \alpha^3 &=\alpha+ 1\\ \alpha^4 &=\alpha^2+ \alpha \end{aligned} &&\begin{aligned} \alpha^5 &=\alpha^2+\alpha+ 1\\ \alpha^6 &=\alpha^2+1 \end{aligned} &&\begin{aligned} \alpha^7 &= 1\\ & \end{aligned} \end{align*}\] and thus $\alpha$ generates the entire multiplicative group. An irreducible polynomial $p(\alpha)$ is called primitive if $\alpha$ generates the entire multiplicative group.

A priori it is not clear that there always exists an invertible element that generates the group and that there exists a primitive polynomial of any degree. For instance, if we consider $\mathbb{F}_{16}$ specified by the polynomial $\alpha^4+\alpha^3+\alpha^2+\alpha+ 1$, then it is easy to see that \[\begin{align*} \alpha^5&=(\alpha + 1)(\alpha^4 + \alpha^3+ \alpha^2+\alpha + 1) + 1 = 1\\ (\alpha^3+\alpha^2)^3% &=\alpha^6\cdot(\alpha+1)^3=\alpha\cdot(\alpha^3+\alpha^2+\alpha+ 1)=1 \end{align*}\] and thus there are indeed elements that have order $5$ and order $3$.

To prove the Theorem, i. e. that there always exists an element that generates the entire multiplicative group, we need the following lemma and its corollary. (To understand how to find a generator of the multiplicative group, you should see the proofs of the corollary and the theorem; the proof of the lemma is nice but not important for this purpose.)

Proof of Lemma.

Proof of Corollary.

Sketch of the proof of the Theorem.

To illustrate the constructive element in the proof, recall that $\mathrm{ord}(\alpha)=5$ and $\mathrm{ord}(\alpha^3+\alpha^2)=3$ in our example field. Thus the order of $\alpha^4+\alpha^3=\alpha^2+\alpha+ 1$ must be $15$ according to Lemma (Combination of coprime orders). To check this, we must compute the third and fifth power of $\alpha^2+\alpha+1$ and check that these are not $1$ (since the order of any element in the multiplicative group of $\mathbb F_{16}$ is $1$, $3$, $5$ or $15$, and we want to exclude the first three possibilities). We have \[\begin{align*} (\alpha^2+\alpha+ 1)^3% &=\alpha^3(\alpha^3+\alpha^2)^3=\alpha^3,\\ (\alpha^2+\alpha+ 1)^5&=\alpha^5(\alpha^3+\alpha^2)^2=\alpha^2+\alpha+ 1.% \end{align*}\] So the order of $\alpha^2+\alpha+ 1$ is indeed $15$.

Let's ponder a little about the meaning of the theorem we just proved.

It is obvious that the additive group of every residue class field $\mathbb F_p = \mathbb Z_p$ is generated by a single element: for example, the group $(\mathbb F_p; +)$ is generated by the residue class of $1$ since every element of $\mathbb F_p$ can be obtained as a multiple of $1$, i. e. as a sum $1 + 1 + \ldots + 1$. As a special case, our theorem says that the multiplicative group of $\mathbb F_p$ is actually generated by a single element too: for example, all non-zero elements of $\mathbb F_7$ are powers of $3$, i. e. obtainable as products $3 \cdot 3 \cdot \ldots \cdot 3$ modulo $7$. On the diagram below, the elements of $\mathbb F_7$ are depicted, with a blue arrow denoting addition of $1$ and red arrow denoting multiplication by $3$. The blue arrows form a cycle comprising all the elements of $\mathbb F_7$ and the red arrows form a cycle comprising all the elements of the multiplicative group, i. e. the non-zero elements. On the diagram on the right, the non-zero elements are rearranged to untangle the red cycle. A group generated by one element is called cyclic by algebraists; the diagrams explain why.

When considering finite fields that are not residue class fields, i. e. fields $\mathbb F_{p^k}$ with $k > 1$, the additive group is not cyclic anymore. For example, in $\mathbb F_{2^k}$ adding any element to itself gives $0$, so the order of any element in the additive group not greater than $2$. However, the theorem says that the multiplicative group is still cyclic! On the diagrams below, the field $\mathbb F_8$ is depicted, with each element denoted by the coefficients of polynomial, e. g. $101$ on the diagram means the polynomial $1 \alpha^2 + 0 \alpha + 1 = \alpha^2 + 1$. On the diagram on the left, the arrow denotes addition of the element $001$, i. e. the constant polynomial $1$. We see that the elements of $\mathbb F_8$ do not form a cycle in this diagram (this diagram by itself does not prove that the additive group of $\mathbb F_8$ is not cyclic: it only shows that $001$ does not generate the group but it does not prove that there does not exist some other element that generates it). The diagram on the right shows that the multiplicative group of $\mathbb F_8$ (when defined by the polynomial $\alpha^3+\alpha+ 1$, as in the example above) is cyclic since the element $010$, i. e. the polynomial $\alpha$, generates it.

The following picture represents the multiplicative subgroup of our other example group above: $\mathbb F_{16}$, defined by $\alpha^4+\alpha^3+\alpha^2+\alpha+ 1$. The red arrows forming the circle show that the element $0111 = \alpha^2+\alpha+ 1$ indeed generates the multiplicative subgroup. Each blue arrow corresponds to multiplication by $0010 = \alpha$ and each gray arrow corresponds to multiplication by $1101 = \alpha^2 + \alpha + 1$. As the blue arrows form a pentagon and the gray arrows a triangle, the orders of $0010$ and $1101$ are $5$ and $3$, respectively.

Actually it is easy to tell whether an element $x$ is a generator of the multiplicative group or not, if it is represented as a power of a generator, i. e. in the form $x = a^k$. For example, $1101 = 0111^{5}$, thus multiplication of an element by $1101$ means multiplication by $0111$ repeated $5$ times, i. e. one gray arrow is equivalent to jumping forward by $5$ in the red cycle. Now note that the group order $15$ is exactly divisible by $5$, so, starting from the identity element $0111^0 = 0001$ and following the gray arrows, we will after $15/5=3$ jumps be back at the beginning and thus $1101$ has no chance of generating the whole multiplicative group. With the element $0010$ it's a little less obvious why it cannot be a generator, since $0010 = 0111^6$ but $15$ is not divisible by $6$. However, note that $15$ and $6$ have a common divisor $3$ and thus, if we start going from the identity element, then even after wrapping around modulo $15$, the blue arrows can only reach elements $0111^k$ where $k$ is divisible by three.

One consequence of the theorem is that multiplication in a finite field becomes very easy if we represent any non-zero element $x$ in memory by storing the exponent $i$ such that $a^i = x$: the task of multiplying two elements will only require the addition of two integers (since $a^i a^j = a^{i+j}$) instead of calculating the product of two polynomials and then applying polynomial long division (which, as we saw earlier, is the way to multiply elements of finite fields if an element are represented by its polynomial's coefficients). Moreover, thanks to the fact that $a^{p^k-1} = 1$ (which holds because of the generalized Fermat's Little Theorem proven in the previous lesson), we have $a^{i+j} = a^{(i+j) \operatorname{mod} (p^k-1)}$, so we can store and add exponents modulo $p^k-1$ (otherwise we could get in trouble because we would get integer overflow if we multiplied many things together).

Unfortunately, while multiplication is easy in the exponent representation, addition becomes very difficult, and therefore this representation often cannot be used in practice. Nevertheless, even knowing that such a representation exists gives valuable insight into the multiplicative structure of finite fields, which can be used to discover their properties, as we shall see in the next lesson.