I’ve been studying a bunch of cryptography lately, and I thought it would be nice to present finite fields in some relatively easy to understand way that doesn’t require too much prior knowledge. All that is really needed here is a basic understanding of fields from an abstract algebra class and some introductory number theory.
We say a field with multiplicative identity has characteristic if . If is infinite then it has characteristic . We are primarily interested in the finite case.
We get this nice little corollary: Let be a field of positive characteristic . Then is prime.
Proof: Suppose is not prime. Then and , so has zero divisors and is not a field.
Here is another really easy to understand corollary: Let be a field of characteristic . Then is a vector space over .
Proof: Trivial. Just write out the canonical action via and everything just works.
If you’ve taken any sort of linear algebra, we now realize that because is finite dimensional over , we can write , and the standard notation for this is .
The obvious question now is, given , can we construct a field of that size, and the answer is yes. Let be an irreducible polynomial in of degree . I claim is a field of size and characteristic .
Proof: Characteristic is quite easily seen because of the base ring taking coefficients in . To see that this quotient has elements, we can see that each of the polynomials of of degree less than are distinct and there are precisely of those. For polynomials of degree at least , we can replace them with polynomials of degree less than , so this works. More precisely, for each term of degree , we can find a polynomial of of degree such that has degree less than because is a field and we repeat until the degrees are within the desired range.
Okay, so this is at least a ring, but how are we so sure that it is a field? One easy way to see this comes from the theory of commutative rings. If is a commutative ring and is a maximal ideal, then is a field, and is maximal if and only if is irreducible (the ideal generated by one of the factors is a “larger” ideal). We will prove the previous statement.
Proof: Let be commutative and be a maximal ideal. Let be non-zero so that is non-zero. Define . This is clearly non-empty so take and write , where it becomes quite obvious that . Now take some , compute , so is also an ideal. On the other hand, we have , but and , so , but is maximal so , so , or there exists such that , or , and .
So now all that remains is to show that there is always some irreducible polynomial and we can always construct a finite field. We will need the following useful theorems.
Theorem 1: If is a finite field, then the group of units is cyclic and there is a generator with order .
Proof: We follow the classical proof of showing the existence of primitive roots modulo . In fact, this is precisely the analogous statement for primitive roots modulo but for finite fields.
Let . For all , we define the set . Any element has an order that divides , so this forms a partition. Namely,
I claim for any we have . If is empty, we are done so pick any element of order from . In particular, this means that are distinct solutions of . This polynomial has at most solutions in and thus in as well (it’s easy to check that zero is not a solution). Hence if we pick arbitrary , there exists some such that , but the order of is precisely , so . The set has precisely elements, and is a subset of that, which gives us the result.
We then recall that the sum
This implies that via a simple size argument. In particular, we now know that and any element of should generate by definition.
Theorem 2: The product of all irreducible monic polynomials such that is .
Proof: Let be this product. is squarefree in because it is relatively prime to its derivative, which is . Thus to show that , we only need to show that they share the same monic irreducible factors.
Let be a monic irreducible factor of of degree . Then is a finite field with elements. I claim that for all . Write . We have, by the freshman dream, the following computation.
where the final equality stems from the fact that . Now pick of order , so we obtain , so monic irreducible factors of have degree that divides .
Now take some that is monic, irreducible, and of degree . Take as a field with elements, so . Since , we easily obtain , which is what we needed.
Corollary: If is the number of monic irreducible polynomials in of degree , then
Proof: We know that is the product of all monic irreducible polynomials with degree dividing . Taking the degrees of both sides of this equality yields
which is precisely what we wanted.
Another corollary: for all .
Proof: We take the Möbius inversion of the above equality. In particular, this yields,
Note that so the RHS is most definitely positive, so .
All that is really left to show for basic properties of finite fields is that they are unique up to isomorphism. Namely, if are both irreducible polynomials of the same degree, then . I leave this as an exercise to the reader.
So why finite fields? Well a lot of modern cryptography is done over finite fields. Namely, AES does computations in . Elliptic curves can also be defined over any field. In particular, cryptography is interested in the case where the fields are finite. Elliptic curves over presents a lot of rich structure as well, but is not of any real cryptographic use to my knowledge. More specifically, standard ECC and ECDH can be done over any finite field, but in the case of SIDH (supersingular isogeny Diffie-Hellman), our curves are over . Visually, it makes absolutely no sense to visualize polynomials as coordinate points but the algebra checks out and that’s all you really need to care about. Visualizations over and maybe should give you enough intuition to work in other fields. Anyways, I am excited to see more uses of finite fields to confuse a bunch of aspiring CS students as well as whatever people will use it for in the future.