====== - #7 Multiplicative group in finite fields ======

In this lesson we shall prove the following theorem and study its consequences.
<WRAP def> **Theorem.** 
Let $\mathbb{F}_{p^k}$ be finite field. Then there exists an element
$a\in\mathbb{F}_{p^k}$ that generates the entire multiplicative group.
</WRAP>
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.)

<WRAP def> **Lemma (Combination of coprime orders).**<BOOKMARK:lemma_coprime_order_combination>
If two elements $x$ and $y$ of an abelian group have coprime orders $i$ and $j$, then their product $xy$ has order $ij$.
</WRAP>

<WRAP def> **Corollary (Combination of orders).**<BOOKMARK:corollary_order_combination>
If two elements $x$ and $y$ of an abelian group have orders $i$ and $j$, then there exists an element $z$
which has order $\operatorname{lcm}(i, j)$.
</WRAP>

++++Proof of Lemma.|
Let $x$ and $y$ be elements of an abelian group, with coprime orders $i$ and $j$, respectively. Then the order of $xy$ is at most $ij$ because $(xy)^{ij} = x^{ij} y^{ij} = (x^{i})^j (y^{j})^i = 1^i 1^j = 1$. To prove that the order of $xy$ is $ij$, we suppose that $(xy)^{k} = 1$ for some $0 < k < ij$ and we will show this gives a contradiction. The least common multiple of $i$ and $j$ is $\operatorname{lcm}(i,j) = \frac{ij}{\gcd(i,j)} = ij$. As $0 < k < ij = \operatorname{lcm}(i,j)$, the number $k$ is either not divisible by $i$ or not divisible by $j$ or not divisible by either. Let us assume that $k$ is not divisible by $i$ (we can do this without loss of generality, as in the case when $k$ is divisible by $i$ but not divisible by $j$ we could simply exchange $i$ and $j$). Then $jk$ is not divisible by $i$ (thanks to $\gcd(i,j) = 1$). Therefore $x^{jk} \neq 1$ (because different powers of an element modulo its order are different, as we saw in lesson [[06_groups]]). On the other hand, we have $y^{jk} = (y^j)^k = 1^k = 1$, and so $(xy)^{jk} = x^{jk}y^{jk} = x^{jk} \neq 1$. This is a contradiction since $(xy)^{jk} = ((xy)^k)^j = 1^j = 1$.
++++

++++Proof of Corollary.|
Let us prove that there exist two numbers $k$ and $l$ such that $kl = \operatorname{lcm}(i, j)$ and the group contains an element $u$ of degree $k$ and an element $v$ of degree $l$. By the lemma above, the product $uv$ would then be an element of degree $\operatorname{lcm}(i, j)$, and the claim would follow.

First note that given a group element $a$ of order $m$, there exist elements of all orders dividing $m$: if $n$ is a positive integer dividing $m$, then $a^d$ is an element of order $n$ where $d = \frac{m}{n}$. Indeed, the order of $a^d$ is no larger than $n$ since $(a^d)^n = a^{dn} = a^m = 1$, and it cannot be smaller either since if we had $(a^d)^s = 1$ for some positive integer $s < n$, then we would have $a^{ds} = 1$ with $0 < ds < m$, contradicting the fact that $\operatorname{ord} a = m$.

Therefore, if we could prove that there exist coprime $k$ and $l$ such that $kl = \operatorname{lcm}(i, j)$ and $k \mid i$ and $l\mid j$, then the corollary would be proven, since we could take $u = x^{\frac{i}{k}}$ and $v = y^{\frac{j}{l}}$.

So it remains to prove that for any positive integers $i$ and $j$ there always exist coprime $k$ and $l$ such that $kl = \operatorname{lcm}(i, j)$ and $k\mid i$ and $l\mid j$. This is easy if we use the fact that any positive integer is a representable as a product of powers of different primes: we put into $k$ all the prime factors, whose power in $i$ is greater than their power in $j$, and into $l$ all the other prime factors. For example, if $i = 2^3 \cdot 5^2 \cdot 7$ and $j = 2^{14} \cdot 3^3 \cdot 5$ then we may take $k = 5^2 \cdot 7$ and $l = 2^{14} \cdot 3^3$.
++++

++++Sketch of the proof of the Theorem. |
First, note that we can find an element such that the orders of
other invertible elements divide its order. If this is not the case, then
we can use [[#corollary_order_combination|Corollary (Combination of orders)]] to resolve violations
one by one. Let $r$ be the final order of this element. Then
obviously all elements of the field are roots of a polynomial
$X\cdot (X^r-1)$. By the Little Bézout's theorem this polynomial can have at
most $r+1$ distinct roots over any field. Consequently, $r=p^k-1$ or
otherwise the field must contain less than $p^k$ elements. The claim
follows as we have shown that $r=p^k-1$.
++++

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_coprime_order_combination|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.

<columns 100% center middle 50% center middle ->
{{z7_plus1_times3.png}}
<newcolumn>
{{z7_times3.png}}
</columns>

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.

<columns 100% center middle 50% center middle ->
{{f8_plus001.png}}
<newcolumn>
{{f8_times010_mod1011.png}}
</columns>

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$.
{{ :finite_fields:f16_times0111_mod11111.png |}}
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. 

<WRAP task>
Find all elements of $\mathbb{F}_{16}$ that generate the entire multiplicative group if the field is specified by the polynomial $\alpha^4+\alpha^3+ \alpha^2+\alpha+ 1$.
++++ Solution. | These are exactly the powers of the generator where the greatest common divisor of the power with the group order is one, i. e. elements $0111^k$ where $\operatorname{gcd}(k, 15) = 1$. From the diagram above, we see that these elements are
  * $0111^1 = 0111$,
  * $0111^2 = 1010$,
  * $0111^4 = 0110$,
  * $0111^7 = 1110$,
  * $0111^8 = 1011$,
  * $0111^{11} = 0101$,
  * $0111^{13} = 0011$ and
  * $0111^{14} = 1001$.
(These are also exactly the elements on the diagram that are not touched by either the pentagon nor the triangle, since a number is coprime to $15$ if and only if it is not divisible by neither $3$ nor $5$; the pentagon touches all powers divisible by $3$ and the triangle all powers divisible by $5$.)
++++
</WRAP>

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.


<WRAP nl>
[[08_subfields]]
</WRAP>