Topics in Galois Fields

In this preliminary chapter, we lay the algebraic foundations which we believe are necessary to understand the theory of finite fields and their applications. Although most of this chapter is certainly covered by many text books on Algebra, we decided to include this background material for the convenience of the reader. This not only serves to present the material in a manner as self-contained as possible but also to fix notations used throughout this book.

This chapter presents the fundamental properties of polynomials and, more generally, formal power series. Besides standard topics such as the evaluation of polynomials, roots, formal derivatives, interpolation and the like, we also consider two more advanced topics which will be important for later chapters, namely Möbius inversion and endomorphisms of vector spaces and their minimal polynomials.

The present chapter is devoted to the basic theory of finite fields, including existence and uniqueness theorems as well as the main structural results. For this purpose, we also extend the fundamental material covered in Chapters 1 and 2 by proving several results on field extensions in general (in particular, in the first two sections).

In the present chapter, we study the algebraic closure of a Galois field. For this purpose, we also provide some basic results on algebraic extensions, extending the material covered in Chapterss 2 and 3.

In contrast to the theoretical construction of finite fields as splitting fields presented in Chap. 3, we now consider the explicit description of the extension field GF(qⁿ) of F = GF(q) as the factor ring F[x] · (f) of the polynomial ring F[x] with respect to an irreducible polynomial f of degree n. Not surprisingly, this will require irreducibility criteria for certain types of polynomials, in particular, for binomials and trinomials. The closely related problems of testing an arbitrary monic polynomial f over F for irreducibility or, more generally, of decomposing f into irreducible polynomials will be postponed to Chap. 6. Thus the main topic of the present chapter is the construction of some irreducible polynomial of any given degree over any given Galois field GF(q), but we will also consider this problem for two important special types of polynomials (namely primitive and self-reciprocal polynomials) in the final two sections.

The topic of the present chapter is the factorization of univariate polynomials over finite fields, with emphasis on the methods of Berlekamp and of Niederreiter.Nevertheless, some of the ideas work for perfect fields in general, and therefore we will restrict attention to finite fields only where necessary. The first two sections are devoted to two particular partial factorizations of a polynomial, the square-free factorization and the distinct degree factorization. After that we develop the method of Berlekamp in Sections 6.3-6.5. In Sections 6.6, 6.8 and 6.9 we discuss the method of Niederreiter, and in Section 6.7 connections between the Berlekamp algebra and the Niederreiter space associated to a polynomial are studied.

In this chapter, we study several aspects of matrices over finite fields. We begin with some basic results on the rank and order of matrices and then apply some of these results to discuss an interesting theoretical topic, namely matrix representations of an extension field \({\text{GF}}(q^{n} )\) over \({\text{GF}}(q)\). Following this, we provide results on the numbers of matrices over \({\text{GF}}(q)\) of various important special types – such as symmetric, orthogonal and circulant matrices – that will be needed later to study basis representations of extension fields. Last but not least, we also consider the Discrete Fourier Transform, which is not only a very useful tool for some results given in the present chapter, but has many interesting further applications.

The main topic of the present chapter is a detailed study of the interaction between theoretical results on various types of bases used to represent finite extension fields \(E = {\text{GF}}(q^{n} )\) over \({\text{GF}}(q)\) and their application to efficiently performing the arithmetic operations in E, with particular emphasis on hardware implementations. Such questions are of fundamental importance for various practical applications, in particular, in Cryptography, Coding Theory, and Signal Processing. We also briefly discuss an alternative approach to the arithmetics of finite fields, namely discrete logarithms, which is likewise useful in some applications.

In Chapter 8, we already encountered linear feedback shift registers in connection with the hardware implementation of arithmetics in GF(2ⁿ): In the present chapter, we will study the sequences produced by such devices—that is, shift register sequences—in detail. As we shall see, these sequences are just the solutions of linear recurrence relations over GF(2): In view of this connection, we will consider shift register sequences over F = GF(q) for general q, and initially even over arbitrary fields F. Even though shift registers (as hardware devices) are of little practical interest for other fields but GF(2), they are a useful concept for visualizing linear recurrences over general fields. In the first two sections, we present some fundamental results which are valid over arbitrary fields F, including characterizations of shift register sequences and results about (ultimately) periodic sequences. After that, we shall restrict ourselves to the case of finite fields; in particular, we will consider shift register sequences associated with irreducible polynomials in Sect. 9.3. In the subsequent two sections, we discuss two applications, namely the construction of pseudo-random sequences and of some cyclic difference sets. We then return to the general theory by considering the notions of the linear complexity and, more strongly, the linear complexity profile of an arbitrary sequence with entries from GF(q). We will describe methods for determining these quantities, in particular the Berlekamp-Massey algorithm. Finally, in Sect. 9.9, we give a further application and study the so-called GMW-sequences, a class of periodic binary sequences which combine good randomness properties with a comparatively high linear complexity.

One of the major problems often encountered in working with finite fields is the transition between their additive and multiplicative structures. We have seen a concrete example of this type of problem when we studied the arithmetics in finite fields in Chap. 8. Depending on the choice of representation, either addition (in some basis representation) or multiplication (using Zech logarithms) is trivial, while the other operation is not at all easy to perform. The same type of problem arises also in theoretical investigations concerning both the additive and multiplicative structure simultaneously, for instance, when proving the existence of primitive normal bases or that of primitive elements with a prescribed value of the trace (into a specified subfield); these two problems will the topic of the final two chapters. Such questions often require the use of tools from Representation Theory which we did not introduce up to now, that is, characters and character sums and, in particular, Gauss sums. These tools will be presented in the current chapter, where we first consider characters of finite abelian groups in general and then specialize to the case of finite fields and introduce the basic properties of Gauss sums. We then give a few interesting applications of the quadratic character; in particular, we shall prove the law of quadratic reciprocity and consider solutions of quadratic equations in several variables over finite fields with odd characteristic. Following this, we shall prove three more advanced identities for Gauss sums; we will also obtain an interesting connection to the eigenvalues of the matrix of the Discrete Fourier Transform defined in Sect. 7.​4. Finally, we extend the DFT to abelian groups in general and present some applications to abelian difference sets and periodic sequences.

The aim of this chapter is to determine a normal element for every extension E/F of finite fields. For this, it will be convenient to work (theoretically) in an algebraic closure \(\widehat{F}\) of a fixed ground field F = GF(q) with q elements. While this will simplify the presentation, it is not actually required for constructing normal elements in specific cases: then all that is really needed are finite extensions of F. Recall from Chap. 4 that for every \(n \in {\mathbb{N}}^{*}\) there is exactly one intermediate field E_n of \(\widehat{F}/F\) with degree n over F. We will explicitly describe a normal element w_n for the extension E_n/F in terms of certain roots of unity whose multiplicative orders depend on q and n. Moreover, we give an inductive construction for a trace-compatible sequence \((w_{n} )_{{n \in {\mathbb{N}}^{*} }}\) over \(\widehat{F}\) for which every w_n is a normal element for E_n/F. Finally, we also present two reasonably efficient algorithms for computing a normal element for an arbitrary extension E = GF(qⁿ) of F = GF(q).

In the present chapter, we consider a particular class of normal elements for extensions of finite fields. We introduce the topic by presenting two examples of normal elements for Galois extensions E/F which are not normal for some intermediate extension E/K of E/F. This suggests to study completely normal elements for E/F, that is, normal elements which are also normal over every intermediate field K of E/F. We first prove the existence of such elements in the more general setting of Galois extensions, before we focus on the construction of completely normal elements in the special case of finite fields. In fact, the main parts of this chapter may be viewed as variations on the themes encountered in Chap. 10; for instance, the class of regular extensions will again play a prominent role. As a result of these deeper investigations, we will obtain an interesting structure theory for extensions of Galois fields.

The topic of this chapter is the celebrated primitive normal basis theorem: for every extension E/F of Galois fields, there exists a primitive element of E which is normal over F. We will provide a complete proof for this fundamental result, which does not rely on the use of computers at all; all necessary calculations can easily be checked using a standard pocket calculator. Nevertheless, such a proof requires a lot of detailed work; an outline of the argument will be provided at the end of the introductory first section.

This final chapter deals with another important result on primitive elements: given an extension E/F of Galois fields with degree n ≥ 2, usually every affine F-hyperplane of E contains a primitive element. The proof will take up almost all of this chapter; some motivation and a detailed outline is provided in the introductory first section. In the final two sections, we consider an interesting application of finite fields for which the strongest known results rely on theorems concerning primitive elements that are quite similar in spirit to those considered in the main part of this chapter and in Chap. 13, and we also include a brief discussion of some existence results for primitive elements satisfying various additional requirements.