Finite Fields for Mortals

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 F with multiplicative identity e has characteristic p if p \cdot e = 0. If F is infinite then it has characteristic 0. We are primarily interested in the finite case.

We get this nice little corollary: Let F be a field of positive characteristic p. Then p is prime.

Proof: Suppose p is not prime. Then p = ab and p \cdot e = ab \cdot e = (a \cdot e) \cdot (b \cdot e) = 0, so F has zero divisors and is not a field.

Here is another really easy to understand corollary: Let F be a field of characteristic p. Then F is a vector space over \ZZ_p = \ZZ/p\ZZ.

Proof: Trivial. Just write out the canonical action via \ZZ_p and everything just works.

If you’ve taken any sort of linear algebra, we now realize that because F is finite dimensional over \ZZ_p, we can write F \simeq (\ZZ_p)^n, and the standard notation for this is F = \FF_{p^n}.

The obvious question now is, given p^n, can we construct a field of that size, and the answer is yes. Let f be an irreducible polynomial in \ZZ_p[X] of degree n. I claim \ZZ_p[X] / \cycgroup{f} is a field of size p^n and characteristic p.

Proof: Characteristic is quite easily seen because of the base ring taking coefficients in \ZZ_p. To see that this quotient has p^n elements, we can see that each of the polynomials of \ZZ_p[X] of degree less than n are distinct and there are precisely p^n of those. For polynomials of degree at least n, we can replace them with polynomials of degree less than n, so this works. More precisely, for each term of degree k \geq n, we can find a polynomial of g of degree k \in \cycgroup{f} such that c_1 X^k - c_2 g has degree less than k because \ZZ_p 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 R is a commutative ring and I is a maximal ideal, then R / I is a field, and \cycgroup{f} is maximal if and only if f is irreducible (the ideal generated by one of the factors is a “larger” ideal). We will prove the previous statement.

Proof: Let R be commutative and I be a maximal ideal. Let [r] \in R / I be non-zero so that r + I is non-zero. Define X = \lbrace i + rs : i \in I, s \in R \rbrace. This is clearly non-empty so take x, y \in X and write x = i_1 + rs_1, y = i_2 + rs_2, where it becomes quite obvious that x + y \in X. Now take some X \ni x = i + rs, s' \in R, compute xs' = is' + rss' = s'x, so X is also an ideal. On the other hand, we have I \subseteq X \subseteq R, but r \not \in I and r \in X, so I \subset X \subseteq R, but I is maximal so X = R, so 1 \in X, or there exists i \in I, s \in R such that 1 = i + rs, or 1 + I = rs + I = (r + I) (s + I), and s + I = [s] = [r]^{-1}.

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 K is a finite field, then the group of units K^* is cyclic and there is a generator x \in K^* with order |K| - 1.

Proof: We follow the classical proof of showing the existence of primitive roots modulo p. In fact, this is precisely the analogous statement for primitive roots modulo p but for finite fields.

Let K = \FF_{p^n}. For all d \mid p^n - 1, we define the set A_d = \lbrace f \in K : \ord(f) = d \rbrace. Any element has an order that divides |K^*|, so this forms a partition. Namely,

    \[ \sum_{d \mid p^n - 1} |A_d| = |K^*| = p^n - 1. \]

I claim for any d we have |A_d| \leq \varphi(d). If |A_d| is empty, we are done so pick any element a of order d from A_d. In particular, this means that 1, a, a^2, \dots, a^{d - 1} are distinct solutions of X^d = 1. This polynomial X^d - 1 has at most d solutions in K and thus in K^* as well (it’s easy to check that zero is not a solution). Hence if we pick arbitrary x \in A_d, there exists some 0 \leq i \leq d - 1 such that a^i = x, but the order of x is precisely d, so \gcd(i, d) = 1. The set \lbrace a^i \mid \gcd(i, d) = 1 \rbrace has precisely \varphi(d) elements, and A_d is a subset of that, which gives us the result.

We then recall that the sum

    \[ \sum_{d \mid n} \varphi(d) = n. \]

This implies that |A_d| = \varphi(d) via a simple size argument. In particular, we now know that |A_{p^n - 1}| \geq 1 and any element of A_{p^n - 1} should generate \FF_{p^n} by definition.

Theorem 2: The product of all irreducible monic polynomials f \in \FF_p[X] such that \deg(f) \mid n is X^{p^n} - X.

Proof: Let P be this product. P is squarefree in \FF_p[X] because it is relatively prime to its derivative, which is -1. Thus to show that P = X^{p^n} - X, we only need to show that they share the same monic irreducible factors.

Let f be a monic irreducible factor of X^{p^n} - X of degree d. Then K = \FF_p[X] / \cycgroup{f} is a finite field with p^d elements. I claim that x^{p^n} = x for all x \in K. Write x = a_0 + a_1 X + \cdots + a_{d - 1} X^{d - 1}. We have, by the freshman dream, the following computation.

    \[ \begin{aligned} x^{p^n} &= (a_0 + a_1 X + \cdots + a_{d - 1} X^{d - 1})^{p^n} \\ &= a_0^{p^n} + a_1^{p^n} X^{p^n} + \cdots + a_{d - 1}^{p^n} X^{(d - 1) p^n} \\ &= a_0 + a_1 X^{p^n} + \cdots + a_{d - 1} X^{(d - 1) p^n} \\ &= a_0 + a_1 X + \cdots + a_{d - 1} X^{d - 1} \\ &= x, \\ \end{aligned} \]

where the final equality stems from the fact that X^{c p^n} - X^c = (X^{p^n} - X)(\dots) \in \cycgroup{f}. Now pick x \in K^* of order p^d - 1, so we obtain p^d - 1 \mid p^n - 1 \iff d \mid n, so monic irreducible factors of X^{p^n} - X have degree that divides n.

Now take some f \in \FF_p[X] that is monic, irreducible, and of degree d \mid n. Take K = \FF_p[X] / \cycgroup{f} as a field with p^d elements, so X^{p^d} = X. Since d \mid n, we easily obtain X^{p^n} = X, which is what we needed.

Corollary: If N_n is the number of monic irreducible polynomials in \FF_p[X] of degree n, then

    \[ p^n = \sum_{d \mid n} d N_d. \]

Proof: We know that X^{p^n} - X is the product of all monic irreducible polynomials with degree dividing n. Taking the degrees of both sides of this equality yields

    \[ p^n &= \sum_{d \mid n} d N_d, \]

which is precisely what we wanted.

Another corollary: N_n > 0 for all n \geq 1.

Proof: We take the Möbius inversion of the above equality. In particular, this yields,

    \[ n N_n = \sum_{d \mid n} \mu \left(\frac{n}{d}\right) p^d. \]

Note that p^n > 1 + p + p^2 + \cdots + p^{n - 1} so the RHS is most definitely positive, so N_n > 0.

All that is really left to show for basic properties of finite fields is that they are unique up to isomorphism. Namely, if f, g are both irreducible polynomials of the same degree, then \ZZ_p[X] / \cycgroup{f} \simeq \ZZ_p[X] / \cycgroup{g}. 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 GF(2^8) \simeq \FF_{2^8}. 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 \CC 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 \FF_{p^2}. 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 \RR and maybe \FF_p 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.

This entry was posted in CTF, Math. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *