Skip to main content

Section 2.5 Finite fields

Prime numbers underlie a significant amount of modern cryptographic methods. We introduce them here to establish the concept of finite fields. We begin with a standard definition.

Definition 2.5.1.
A positive integer \(p\) is called prime if its only positive divisors are \(1\) and \(p\text{.}\) That is, for a prime \(p\text{,}\) if \(d \mid p\) then \(d = 1\) or \(d = p\text{.}\)

It is fortunate that the supply of primes cannot be exhausted. The following theorem is ancient, and appears in Euclid's Elements.

There are many proofs of the following theorem, but perhaps the most standard is a proof by contradiction that uses the definition of divisibility. Look up a proof of the following theorem and try to explain it in plain language to a friend. You will have succeeded if they understand your argument.

When \(p\) is prime, the ring of integers \(\Z_p\) has the property that every nonzero integer modulo \(p\) has a multiplicative inverse, which means that arithmetic becomes completely consistent: we can add, subtract, multiply and divide just like in the real numbers.

If \(a \in \Z_p\) is nonzero, then \(0 \lt a \lt p\text{.}\) Since \(p\) is prime, we have \(\gcd(a,p) = 1\text{,}\) which implies that \(a\) has an inverse mod \(p\text{.}\)

You should notice that you can use the extended Euclidean algorithm to compute the inverse of \(a \bmod p\text{:}\) Since \(\gcd{a,p} = 1\text{,}\) there exists \(u, v\) so that

\begin{equation*} au + pv \equiv 1 \bmod p. \end{equation*}

But then \(p \mid (1 - au)\) (why?) and so by the definition of congruence,

\begin{equation*} au \equiv 1 \bmod p. \end{equation*}

Thus, we can take \(a\inv = u\text{.}\)

\(\Z_p\) is a (commutative) ring with the property that every nonzero element has a multiplicative inverse. Such an object is called a field (examples include the real numbers \(\R\text{,}\) the rational numbers \(\mathbb Q\text{,}\) and the complex numbers \(\C\)). Because \(\Z_p\) has only \(p\) elements, it is an example of a finite field, and usually denoted \(\F_p\text{.}\) Finite fields are an area of study of enormous importance in both pure and applied mathematics, and understanding them is one of the labors of mastering high level cryptography.

From \(\F_p\text{,}\) we can form the group of units \(\F_p\ad\) by just removing \(0\text{,}\) since every nonzero element in \(\F_p\) has a multiplicative inverse modulo \(p\text{.}\) The group of units \(\F_p\ad\) is perhaps the central object of study for the next part of the course.

Exercises Exercises

1.
2.
\(u\)\(v\)\(a \bmod p\)\(a\)\(p\)