Basic Concepts in Number Theory and Finite Fields

Chapter 4 BASIC CONCEPTS IN NUMBER THEORY AND FINITE FIELDS

            Divisibility and The Division Algorithm

            The Euclidean Algorithm

            Modular Arithmetic

            Groups, Rings, and Fields

            Finite Fields of the Form GF(p)

            Polynomial Arithmetic

            Finite Fields of the Form GF(2n)

KEY POINTS

◆                    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 divi- sion by n.

◆                    The greatest common divisor of two integers is the largest positive integer that exactly divides both integers.

◆                    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.

◆                    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 crypto- graphic algorithms rely heavily on properties of finite fields, notably the Advanced Encryption Standard (AES) and elliptic curve cryptography. Other examples include the message authentication code CMAC and the authenticated encryption scheme GMC.

This chapter provides the reader with sufficient background on the concepts of finite fields to be able to understand the design of AES and other cryptographic algorithms that use finite fields. The first three sections introduce basic   concepts from number theory that are needed in the remainder of the chapter; these include divisibility, the Euclidian algorithm, and modular arithmetic. Next comes 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. We

are then ready to discuss finite fields of the form  GF(p), where p is a prime num-

ber. Next, we need some additional background, this time in polynomial arith- metic. The chapter concludes with a discussion of finite fields of the form GF(2n), 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. Accordingly, this chapter and Chapter 8 include a number of examples, each of which is highlighted in a shaded  box.