This book is designed as a textbook edition of our monograph Finite Fields which appeared in 1983 as Volume 20 of the Encyclopedia of Mathematics and Its Applications. Several changes have been made in order to tailor the book to the needs of the student. The historical and bibliographical notes at the end of each chapter and the long bibliography have been omitted as they are mainly of interest to researchers. The reader who desires this type of information may consult the original edition. There are also changes in the text proper, with the present book having an even stronger emphasis on applications. The increasingly important role of finite fields in cryptology is reflected by a new chapter on this topic. There is now a separate chapter on algebraic coding theory containing material from the original edition together with a new section on Goppa codes. New material on pseudorandom sequences has also been added. On the other hand, topics in the original edition that are mainly of theoretical interest have been omitted. Thus, a large part of the material on exponential sums and the chapters on equations over finite fields and on permutation polynomials cannot be found in the present volume.

The theory of finite fields is a branch of modern algebra that has come to the fore in the last 50 years because of its diverse applications in combinatorics, coding theory, cryptology, and the mathematical study of switching circuits, among others.

The theory of polynomials over finite fields is important for investigating the algebraic structure of finite fields as well as for many applications. Above all, irreducible polynomials—the prime elements of the polynomial ring over a finite field—are indispensable for constructing finite fields and computing with the elements of a finite field.

Section 1 introduces the notion of the order of a polynomial. An important fact is the connection between minimal polynomials of primitive elements (so-called primitive polynomials) and polynomials of the highest possible order for a given degree. Results about irreducible polynomials going beyond those discussed in the previous chapters are presented in Section 2. The next section is devoted to constructive aspects of irreducibility and deals also with the problem of calculating the minimal polynomial of an element in an extension field.

Certain special types of polynomials are discussed in the last two sections. Linearized polynomials are singled out by the property that all the exponents occurring in them are powers of the characteristic. The remarkable theory of these polynomials enables us, in particular, to give an alternative proof of the normal basis theorem. Binomials and trinomials — that is, two-term and three-term polynomials—form another class of polynomials for which special results of considerable interest can be established. We remark that another useful collection of polynomials— namely, that of cyclotomic polynomials—was already considered in Chapter 2, Section 4, and that some additional information on cyclotomic polynomials is contained in Section 2 of the present chapter.

This book has been out of print for some time, but because of the continuing demand we want to make it available again. We have taken this opportunity to revise the book slightly. Historical and bibliographical notes have been added to each chapter, the bibliography has become more detailed, and the misprints in the original edition have of course been corrected. We would like to thank the staff at Cambridge University Press for accommodating our wishes so readily.

The subject of finite fields has undergone a spectacular development in the last 10 years. Great strides have been made, especially in the computational and algorithmic aspects of finite fields which are important in the rapidly developing areas of computer algebra and symbolic computation. The numerous applications of finite fields to combinatorics, cryptology, algebraic coding theory, pseudorandom number generation and electrical engineering, to name but a few, have provided a steady impetus for further research. Thus, the subject grows inexorably. Nevertheless, we hope that this book will continue to serve its purpose as an introduction for students, since it is devoted mainly to those parts that have a certain quality of timelessness, namely the classical theory and the standard applications of finite fields.

In this chapter we consider some aspects of cryptology that have received considerable attention over the last few years. Cryptology is concerned with the designing and the breaking of systems for the communication of secret information. Such systems are called cryptosystems or cipher systems or ciphers. The designing aspect is called cryptography, the breaking is referred to as cryptanalysis. The rapid development of computers, the electronic transmission of information, and the advent of electronic transfer of funds all contributed to the evolution of cryptology from a government monopoly that deals with military and diplomatic communications to a major concern of business. The concepts have changed from conventional (private-key) cryptosystems to public-key cryptosystems that provide privacy and authenticity in communication via transfer of messages. Cryptology as a science is in its infancy since it is still searching for appropriate criteria for security and measures of complexity of cryptosystems.

Conventional cryptosystems date back to the ancient Spartans and Romans. One elementary cipher, the Caesar cipher, was used by Julius Caesar and consists of a single key K = 3 such that a message M is transformed into M + 3 modulo 26, where the integers 0, 1, …, 25 represent the letters A, B, …, Z of the alphabet. An obvious generalization of this cipher leads to the substitution ciphers often named after de Vigenère, a French cryptographer of the 16th century.

Any nonconstant polynomial over a field can be expressed as a product of irreducible polynomials. In the case of finite fields, some reasonably efficient algorithms can be devised for the actual calculation of the irreducible factors of a given polynomial of positive degree.

The availability of feasible factorization algorithms for polynomials over finite fields is important for coding theory and for the study of linear recurrence relations in finite fields. Beyond the realm of finite fields, there are various computational problems in algebra and number theory that depend in one way or another on the factorization of polynomials over finite fields. We mention the factorization of polynomials over the ring of integers, the determination of the decomposition of rational primes in algebraic number fields, the calculation of the Galois group of an equation over the rationals, and the construction of field extensions.

We shall present several algorithms for the factorization of polynomials over finite fields. The decision on the choice of algorithm for a specific factorization problem usually depends on whether the underlying finite field is “small” or “large.” In Section 1 we describe those algorithms that are better adapted to “small” finite fields and in the next section those that work better for “large” finite fields. Some of these algorithms reduce the problem of factoring polynomials to that of finding the roots of certain other polynomials. Therefore, Section 3 is devoted to the discussion of the latter problem from the computational viewpoint.

Finite fields play a fundamental role in some of the most fascinating applications of modern algebra to the real world. These applications occur in the general area of data communication, a vital concern in our information society. Technological breakthroughs like space and satellite communications and mundane matters like guarding the privacy of information in data banks all depend in one way or another on the use of finite fields. Because of the importance of these applications to communication and information theory, we will present them in greater detail in the following chapters. Chapter 8 discusses applications of finite fields to coding theory, the science of reliable transmission of messages, and Chapter 9 deals with applications to cryptology, the art of enciphering and deciphering secret messages.

This chapter is devoted to applications of finite fields within mathematics. These applications are indeed numerous, so we can only offer a selection of possible topics. Section 1 contains some results on the use of finite fields in affine and projective geometry and illustrates in particular their role in the construction of projective planes with a finite number of points and lines. Section 2 on combinatorics demonstrates the variety of applications of finite fields to this subject and points out their usefulness in problems of design of statistical experiments.

In Section 3 we give the definition of a linear modular system and show how finite fields are involved in this theory.

This introductory chapter contains a survey of some basic algebraic concepts that will be employed throughout the book. Elementary algebra uses the operations of arithmetic such as addition and multiplication, but replaces particular numbers by symbols and thereby obtains formulas that, by substitution, provide solutions to specific numerical problems. In modern algebra the level of abstraction is raised further: instead of dealing with the familiar operations on real numbers, one treats general operations —processes of combining two or more elements to yield another element—in general sets. The aim is to study the common properties of all systems consisting of sets on which are defined a fixed number of operations interrelated in some definite way—for instance, sets with two binary operations behaving like + and · for the real numbers.

Only the most fundamental definitions and properties of algebraic systems—that is, of sets together with one or more operations on the set—will be introduced, and the theory will be discussed only to the extent needed for our special purposes in the study of finite fields later on. We state some standard results without proof. With regard to sets we adopt the naive standpoint. We use the following sets of numbers: the set ℕ of natural numbers, the set ℤ of integers, the set ℚ of rational numbers, the set ℝ of real numbers, and the set ℂ of complex numbers.

Introduction

The Customer Access Network (CAN) is that part of the telecommunications network located between the local exchange and the customer's premises. Traditionally, a star network architecture based on twisted copper pairs has been used; however, this is unable to meet the requirements of future broadband services. Due to the number of premises connected, the CAN represents a substantial proportion of the total capital investment in the Australian telecommunications network. To prevent the need for subsequent upgrading, it is desirable to ‘future-proof’ any alterations to the CAN by providing a transmission medium capable of meeting future needs.

Over the next few years, optical fibre will be progressively introduced into the CAN, providing broadband access to the customer. Current costs associated with optical equipment make the cost of a dedicated fibre CAN (ie a simple star architecture) prohibitive. One of the most promising schemes for early introduction of fibre to the CAN is the Multiple Access Customer Network (MACNET) [5,6,7].

Introduction

The Frequency Management Problem is a special case of a general NP-Complete problem called the ‘Consistent Labelling Problem” [8] or the ‘Constraint Satisfaction Problem’ [3], in either case abbreviated as CLP. This problem consists of a list of N units (or ‘variables’), U = (u1, u2,…,uN), each unit having a set L = (L1,L2,…,LM) of M possible labels (or ‘values’). A consistent labelling f is a relation f: U → L such that for each pair of units and assigned labels, the required constraints are satisfied.

Introduction

In this paper we give a survey of the problem of determining Mordell-Weil groups of universal abelian varieties.

We begin with the pioneering work of Shioda in the early 1970's on elliptic modular surfaces. In many ways, this is the most difficult and intriguing case. Shioda showed that the universal elliptic curve of level N in characteristic zero has only the N-torsion in its Mordell-Weil group over the field of elliptic modular functions of level N. The elliptic modular case is also the only case in which nontrivial examples are known of universal abelian varieties (in positive characteristic) with infinite Mordell-Weil group.

We then turn to abelian varieties (in characteristic zero) of higher dimension, paying special attention to two simple cases. The first, a direct generalization of the elliptic case, is that of the universal principally polarized abelian variety of dimension d > 1 and level N ≥ 3. Two proofs are sketched (Sections 2.2 and 2.7) of Shioda's conjecture that the Mordell-Weil group over the field of Siegel modular functions of level N is exactly the N-torsion (≅ = (Z/NZ)2d). These proofs are given as illustrative examples of some general techniques which were given in [12], [13], and [14]. The second case concerns abelian varieties whose endomorphism algebras contain an order in an indefinite division quaternion algebra over Q.

Introduction

In both commercial and private transactions, authentication of messages is of vital concern. For example, a person accepting a cheque usually insists on some identification of the issuer or authentication of the originator, and the person issuing the cheque not only fills in the face amount in numerals but writes out the amount in words to make it more difficult for anyone to alter the face amount on a cheque bearing his signature. This example illustrates the two main concerns in the authentication of information, namely verification that the communication originated with the purported transmitter and that it has not been subsequently altered. The contemporary concern is with situations in which the exchange involves only information, as for example in Electronic Funds Transfer (EFT).