Finite Fields of The Form GF(p)

4.4. Finite Fields of The Form GF(p)

In Section 4.1, we defined a field as a set that obeys all of the axioms of Figure 4.1 and gave some examples of infinite fields. Infinite fields are not of particular interest in the context of cryptography. However, finite fields play a crucial role in many cryptographic algorithms. It can be shown that the order of a finite field (number of elements in the field) must be a power of a prime pⁿ, where n is a positive integer. We discuss prime numbers in detail in Chapter 8. Here, we need only say that a prime number is an integer whose only positive integer factors are itself and 1. That is, the only positive integers that are divisors of p are p and 1.

The finite field of order pⁿ is generally written GF(pⁿ); stands for Galois field, in honor of the mathematician who first studied finite fields. Two special cases are of interest for our purposes. For n = 1, we have the finite field GF(p); this finite field has a different structure than that for finite fields with n > 1 and is studied in this section. In Section 4.6, we look at finite fields of the form GF(2ⁿ).

Finite Fields of Order p

For a given prime, p, the finite field of order p, GF(p) is defined as the set Z_p of integers {0, 1,..., p 1}, together with the arithmetic operations modulo p.

Recall that we showed in Section 4.2 that the set Z_n of integers {0,1,...,n 1}, together with the arithmetic operations modulo n, is a commutative ring (Table 4.2). We further observed that any integer in Z_n has a multiplicative inverse if and only if that integer is relatively prime to n [see discussion of Equation (4.3)].^[4] If n is prime, then all of the nonzero integers in Z_n are relatively prime to n, and therefore there exists a multiplicative inverse for all of the nonzero integers in Z_n. Thus, we can add the following properties to those listed in Table 4.2 for Z_p:

^[4] As stated in the discussion of Equation (4.3), two integers are relatively prime if their only common positive integer factor is 1.

---

[Page 110]

Multiplicative inverse (w1)	For each w Zp, w 0, there exists a z Zp such that w x z 1 (mod p)

Because w is relatively prime to p, if we multiply all the elements of Z_p by w, the resulting residues are all of the elements of Z_p permuted. Thus, exactly one of the residues has the value 1. Therefore, there is some integer Z_p in that, when multiplied by w, yields the residue 1. That integer is the multiplicative inverse of w, designated w¹. Therefore, Z_p is in fact a finite field. Further, Equation (4.3) is consistent with the existence of a multiplicative inverse and can be rewritten without the condition: