Finite Fields

Finite Fields

4.1 Groups, Rings, and Fields
4.2 Modular Arithmetic
4.3 The Euclidean Algorithm
4.4 Finite Fields of the Form GF(p)
4.5 Polynomial Arithmetic
4.6 Finite Fields of the Form GF(2n)
4.7 Recommended Reading and Web Sites
4.8 Key Terms, Review Questions, and Problems

The next morning at daybreak, Star flew indoors, seemingly keen for a lesson. I said, "Tap eight." She did a brilliant exhibition, first tapping it in 4, 4, then giving me a hasty glance and doing it in 2, 2, 2, 2, before coming for her nut.

It is astonishing that Star learned to count up to 8 with no difficulty, and of her own accord discovered that each number could be given with various different divisions, this leaving no doubt that she was consciously thinking each number. In fact, she did mental arithmetic, although unable, like humans, to name the numbers. But she learned to recognize their spoken names almost immediately and was able to remember the sounds of the names. Star is unique as a wild bird, who of her own free will pursued the science of numbers with keen interest and astonishing intelligence.

Living with Birds, Len Howard

Key Points A field is a set of elements on which two arithmetic operations (addition and multiplication) have been defined and which has the properties of ordinary arithmetic, such as closure, associativity, commutativity, distributivity, and having both additive and multiplicative inverses. Modular arithmetic is a kind of integer arithmetic that reduces all numbers to one of a fixed set [0...n 1] for some number n. Any integer outside this range is reduced to one in this range by taking the remainder after division by n. The greatest common divisor of two integers is the largest positive integer that exactly divides both integers. Finite fields are important in several areas of cryptography. A finite field is simply a field with a finite number of elements. It can be shown that the order of a finite field (number of elements in the field) must be a power of a prime pn, where n is a positive integer. Finite fields of order p can be defined using arithmetic mod p. Finite fields of order pn, for n > 1 can be defined using arithmetic over polynomials.

Finite fields have become increasingly important in cryptography. A number of cryptographic algorithms rely heavily on properties of finite fields, notably the Advanced Encryption Standard (AES) and elliptic curve cryptography.

The chapter begins with a brief overview of the concepts of group, ring, and field. This section is somewhat abstract; the reader may prefer to quickly skim this section on a first reading. Next, we need some elementary background in modular arithmetic and the Euclidean algorithm. We are then ready to discuss finite fields of the form GF(p), where p is a prime number. Next, we need some additional background, this time in polynomial arithmetic. The chapter concludes with a discussion of finite fields of the form GF(2ⁿ) where n is a positive integer.

The concepts and techniques of number theory are quite abstract, and it is often difficult to grasp them intuitively without examples [RUBI97]. Accordingly, this chapter and Chapter 8 include a number of examples, each of which is highlighted in a shaded box.