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.
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 .
(i) (Fermat's little theorem) If , then .
(ii) If , then .
(ii) Clearly, if then this claim is true, while, for , the claim follows from part (i).
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.
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.
By the previous lemma,
We obtain in the same way that .
The homomorphism in the previous lemma is called the Frobenius endomorphism.
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 .
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.
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.
The following theorem describes all subfields of a finite field.
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.
Next we prove an important property of the irreducible polynomials over finite fields.
Moreover, the elements are pairwise distinct.
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.
In this section we characterise certain automorphisms of finite fields.
Recall that the map is defined as follows: where .
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 .
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 .
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.
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.
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,
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).