7.6 Finite fields

Fields are mathematical structures in which the basic arithmetic rules that we are used to hold true: in a field, we can add and multiply things together, and we can also reverse these operations, if we like. If we choose to combine addition and multiplication in a single expression, the so-called distributive law holds, which tells us we can factor common factors out of a sum. We are introducing finite fields here because they provide the stage for another important public-key cryptosystem, the RSA algorithm, which we will cover in Section 7.7, The RSA algorithm. Moreover, we can build other interesting cyclic groups out of finite fields, namely elliptic curves, which will be the subject of Chapter 8, Elliptic Curves.

To begin with, here are the formal requirements for a set M being a field:

• (F1) There is an operation + on M so that (M,+) forms an abelian group with neutral element 0
• (F2) There is an operation ⋅ on M so that (M ∖{0},⋅) forms an abelian group with neutral element 1
• (F3) For all a,b,c ∈ M, we have a ⋅ (b + c) = a ⋅ b + a ⋅ c (Distributive Law)

The most common examples of fields are the real numbers ℝ and the rational numbers ℚ. However, these sets have infinitely many elements, and in order to be usable in a computer, we need fields with a finite number of elements. This crucial number is also called the order of the field.

7.6.1 Fields of order p

In the last section, we already established that for a prime number p, the set M = {0,1,…,p − 1} forms an abelian group with respect to addition modulo p and M ∖{0} = {1,…,p− 1} forms an abelian group with respect to multiplication modulo p. Moreover, the distributive law holds for addition and multiplication modulo p. Thus (M = {0,1,…,p − 1},+,⋅) forms a field with p elements. This field is called 𝔽p. The group 𝔽p∗ = ({1,…,p − 1},⋅) is called the multiplicative group of 𝔽p. It can be shown that the multiplicative groups of finite fields are always cyclic.