5.2. 5.2 Finite fields

Finite fields, that is, fields with a finite number of elements, play an important role in mathematics and in several of its application areas, for instance, in computing. They are also fundamental in many important constructions. In this section we summarise the most important results in the theory of finite fields, putting an emphasis on the problem of their construction.

In this section denotes a prime number, and denotes a power of with a positive integer exponent.

Theorem 5.16 Suppose that is a finite field. Then there is a prime number such that the prime field of is isomorphic to (the field of residue classes modulo ). Further, the field is a finite dimensional vector space over , and the number of its elements is a power of . In fact, if , then .

Proof. The characteristic of must be a prime, say , as a field with characteristic zero must have infinitely many elements. Thus the prime field of is isomorphic to . Since is a subfield, the field is a vector space over . Let be a basis of over . Then each can be written uniquely in the form where . Hence .

In a field , the set of non-zero elements (the multiplicative group of ) is denoted by . From Theorem 5.2 we immediately obtain the following result.

Theorem 5.17 If is a finite field, then its multiplicative group is cyclic.

A generator of the group is said to be a primitive element. If and is a primitive element of , then the elements of are .

Corollary 5.18 Suppose that is a finite field with order and let be a primitive element of . Let be a minimal polynomial of over . Then is irreducible in , the degree of is , and is isomorphic to the field .

Proof. Since the element is primitive in , we have . The rest of the lemma follows from Lemma 5.8 and from Theorem 5.11.

Theorem 5.19 Let be a finite field with order . Then

(i) (Fermat's little theorem) If , then .

(ii) If , then .

Proof. (i) Suppose that is a primitive element. Then we may choose an integer such that . Therefore

(ii) Clearly, if then this claim is true, while, for , the claim follows from part (i).

Theorem 5.20 Let be a field with elements. Then

Proof. By Theorem 5.19 and Lemma 5.5, the product on the right-hand side is a divisor of the polynomial . Now the assertion follows, as the degrees and the leading coefficients of the two polynomials in the equation coincide.

Corollary 5.21 Arbitrary two finite fields with the same number of elements are isomorphic.

Proof. Suppose that , and that both and are fields with elements. Let be a primitive element in . Then Corollary 5.18 implies that a minimal polynomial of over is irreducible (in ) with degree . Further, . By Lemma 5.8 and Theorem 5.19, the minimal polynomial is a divisor of the polynomial . Applying Theorem 5.20 to , we find that the polynomial , and also its divisor , can be factored as a product of linear terms in , and so has at least one root in . As is irreducible in , it must be a minimal polynomial of (see Corollary 5.10), and so is isomorphic to the field . Comparing the number of elements in and in , we find that , and further, that and are isomorphic.

In the sequel, we let denote the field with elements, provided it exists. In order to prove the existence of such a field for each prime-power , the following two facts will be useful.

Lemma 5.22 If is a prime number and is an integer such that , then .

Proof. On the one hand, the number is an integer. On the other hand, is a fraction such that, for , its numerator is divisible by , but its denominator is not.

Lemma 5.23 Let be a commutative ring and let be a prime such that for all . Then the map mapping is a ring homomorphism.

Proof. Suppose that . Clearly,

By the previous lemma,

We obtain in the same way that .

The homomorphism in the previous lemma is called the Frobenius endomorphism.

Theorem 5.24 Assume that the polynomial is irreducible, and, for a positive integer , it is a divisor of the polynomial . Then the degree of divides .

Proof. Let be the degree of , and suppose, by contradiction, that where . The assumption that can be rephrased as . However, this means that, for an arbitrary polynomial , we have

Note that we applied Lemma 5.23 to the ring , and Theorem 5.19 to . The residue class ring is isomorphic to the field , which has elements. Let be a polynomial for which is a primitive element in the field . That is, , but for . Therefore,

and so . Since the residue class ring is a field, , but we must have . As , this contradicts to the primitivity of .

Theorem 5.25 For an arbitrary prime and positive integer , there exists a field with elements.

Proof. We use induction on . The claim clearly holds if . Now let and let be a prime divisor of . By the induction hypothesis, there is a field with elements. By Theorem 5.24, each of the irreducible factors, in , of the the polynomial has degree either 1 or . Further, , and so, by Lemma 5.13, is square-free. Over , the number of linear factors of is at most , and so is the degree of their product. Hence there exist at least polynomials with degree that are irreducible in . Let be such a polynomial. Then the field is isomorphic to the field with elements.

Corollary 5.26 For each positive integer , there is an irreducible polynomial with degree .

Proof. Take a minimal polynomial over of a primitive element in .

A little bit later, in Theorem 5.31, we will prove a stronger statement: a random polynomial in with degree is irreducible with high probability.

Subfields of finite fields.

The following theorem describes all subfields of a finite field.

Theorem 5.27 The field contains a subfield isomorphic to , if and only if . In this case, there is exactly one subfield in that is isomorphic to .

Proof. The condition that is necessary, since the larger field is a vector space over the smaller field, and so must hold with a suitable integer .

Conversely, suppose that , and let be an irreducible polynomial with degree . Such a polynomial exists by Corollary 5.26. Let . Applying Theorem 5.19, we obtain, in , that , which yields . Thus must be a divisor of the polynomial . Using Theorem 5.20, we find that has a root in . Now we may prove in the usual way that the subfield is isomorphic to .

The last assertion is valid, as the elements of are exactly the roots of (Theorem 5.20), and this polynomial can have, in an arbitrary field, at most roots.

The structure of irreducible polynomials.

Next we prove an important property of the irreducible polynomials over finite fields.

Theorem 5.28 Assume that are finite fields, and let . Let be the minimal polynomial of over with leading coefficient , and suppose that . Then

Moreover, the elements are pairwise distinct.

Proof. Let . If with , then, using Lemma 5.23 and Theorem 5.19, we obtain

Thus is also a root of .

As is a root of , the argument in the previous paragraph shows that so are the elements . Hence it suffices to show, that they are pairwise distinct. Suppose, by contradiction, that and that . Let and let . By assumption, , which, by Lemma 5.8, means that . From Theorem 5.24, we obtain, in this case, that , which is a contradiction, as .

This theorem shows that a polynomial which is irreducible over a finite field cannot have multiple roots. Further, all the roots of can be obtained from a single root taking -th powers repeatedly.

Automorphisms.

In this section we characterise certain automorphisms of finite fields.

Definition 5.29 Suppose that are finite fields. The map is an -automorphism of the field , if it is an isomorphism between rings, and holds for all .

Recall that the map is defined as follows: where .

Theorem 5.30 The set of -automorphisms of the field is formed by the maps .

Proof. By Lemma 5.23, the map is a ring homomorphism. The map is obviously one-to-one, and hence it is also an isomorphism. It follows from Theorem 5.19, that leaves the elements fixed. Thus the maps are -automorphisms of .

Suppose that , and with , and that is an -automorphism of . We claim that is a root of . Indeed,

Let be a primitive element of and assume now that is a minimal polynomial of . By the observation above and by Theorem 5.28, , with some , that is, . Hence the images of a generating element of under the automorphisms and coincide, which gives .

The construction of finite fields.

Let . By Theorem 5.7 and Corollary 5.26, the field can be written in the form , where is an irreducible polynomial with degree . In practical applications of field theory, for example in computer science, this is the most common method of constructing a finite field. Using, for instance, the polynomial in Example 5.2, we may construct the field . The following theorem shows that we have a good chance of obtaining an irreducible polynomial by a random selection.

Theorem 5.31 Let be a uniformly distributed random polynomial with degree and leading coefficient . (Being uniformly distributed means that the probability of choosing is .) Then is irreducible over with probability at least .

Proof. First we estimate the number of elements for which . We claim that the number of such elements is at least

where the summation runs for the distinct prime divisors of . Indeed, if does not generate, over , the field , then it is contained in a maximal subfield of , and these maximal subfields are, by Theorem5.27, exactly the fields of the form . The number of distinct prime divisors of are at most , and so the number of such elements is at least . The minimal polynomials with leading coefficients 1 over of such elements have degree and they are irreducible. Such a polynomial is a minimal polynomial of exactly elements (Theorem 5.28). Hence the number of distinct irreducible polynomials with degree and leading coefficient 1 in is at least

from which the claim follows.

If, having , we would like to construct one of its extensions , then it is worth selecting a random polynomial

In other words, we select uniformly distributed random coefficients independently. The polynomial so obtained is irreducible with a high probability (in fact, with probability at least if is large). Further, in this case, we also have . We expect that we will have to select about polynomials before we find an irreducible one.

We have seen in Theorem 5.25 that field extensions can be obtained using irreducible polynomials. It is often useful if these polynomials have some further nice properties. The following lemma claims the existence of such polynomials.

Lemma 5.32 Let be a prime. In a finite field there exists an element which is not an -th power if and only if . If is such an element, then the polynomial is irreducible in , and so is a field with elements.

Proof. Suppose first that and let be a positive integer such that . If such that , then , while if , then . Hence, in this case, each of the elements of is an -th power.

Next we assume that , and we let be a primitive element in . Then, in , the -th powers are exactly the following elements: . Suppose now that , but . Then the order of an element is divisible by if and only if is not an -th power. Let be such an element, and let be an irreducible factor of the polynomial . Suppose that the degree of is ; clearly, . Then is a field with elements and, in , the equation holds. Therefore the order of is divisible by . Consequently, . As is not divisible by , we have . In other words . On the other hand, as , we find , and hence , which, since , can only happen if .

In certain cases, we can use the previous lemma to boost the probability of finding an irreducible polynomial.

Claim 5.33 Let be a prime such that . Then, for a random element , the polynomial is irreducible in with probability at least .

Proof. Under the conditions, the -th powers in constitute the cyclic subgroup with order . Thus a random element is an -th power with probability , and hence the assertion follows from Lemma 5.32.

Remark. Assume that , and, if , then assume also that . In this case there is an element in that is not an -th power. We claim that that the residue class is not an -th power in . Indeed, by the argument in the proof of Lemma 5.32, it suffices to show that . By our assumptions, this is clear if . Now assume that , and write . Then, for all integers , we have , and so, by the assumptions,

Exercises

5.2-1 Show that the polynomial can be factored as a product of linear factors over the field .

5.2-2 Show that the polynomial is irreducible over , that is, . What is the order of the element in the residue class ring? Is it true that the element is primitive in ?

5.2-3 Determine the irreducible factors of over the field .

5.2-4 Determine the subfields of .

5.2-5 Let and be positive integers. Show that there exists a finite field containing such that and . What can we say about the number of elements in ?

5.2-6 Show that the number of irreducible polynomials with degree and leading coefficient 1 over is at most .

5.2-7 (a) Let be a field, let be an -dimensional vector space over , and let be a linear transformation whose minimal polynomial coincides with its characteristic polynomial. Show that there exists a vector such that the images are linearly independent.

(b) A set is said to be a normal basis of over , if and is a linearly independent set over . Show that has a normal basis over .

Hint. Show that a minimal polynomial of the -linear map is , and use part (a).