FINITE FIELDS (CONTINUED): HOW TO CONSTRUCT

MATH 195

[For more on finite fields, consult the treatise by Lidl and Neiddereiter entitled Finite Fields.]

In our dictionary,

𝔽_{p}[X]/(f) = {g : g = 0 or deg g < deg f}

with usual adiition and multiplication modulo f corresponds to

ℤ/nℤ = {0, 1, …, n − 1}

with addition and multiplication modulo n.

For example, if f(X) = X^{8} + X^{4} + X^{3} + X + 1 and b = 00010000 = X^{4} ∈ 𝔽_{2}[X]/(f), then b^{2} = X^{8} = X^{4} + X^{3} + X + 1 = 00011011 by doing long division and reducing modulo f.

Note that for any prime p and polynomial f ∈ 𝔽_{p}[X], there is a map

𝔽_{p}[X] → 𝔽_{p}[X]/(f)
g ↦ g mod f

preserving addition and multiplication, analogous to the map ℤ → ℤ/nℤ. Also, g and h have the same image if and only if they have the same remainder upon division by f, which is to say f divides g − h.

Our motivation to study these algebraic objects was to construct finite fields. Recall that ℤ/nℤ is a field if and only if n is prime. Analogously, 𝔽_{p}[X]/(f) is a field if and only f is irreducible.

Recall that every finite field k has #k = p^{n} = q, a prime power number of elements. Counting, we see that #𝔽_{p}[X]/(f) = p^{deg f}, since we have representatives c_{n−1}c_{n−2} … c_{1}c_{0} if deg f = n.

Conclusion: To construct a finite field of p^{n} elements, it suffices to find a (monic) irreducible polynomial f ∈ 𝔽_{p}[X] of degree n:

f = X^{n} + a_{n−1}X^{n−1} + ⋯ + a_{1}X + a_{0}, a_{i} ∈ 𝔽_{p}.

The field is then 𝔽_{p}[X]/(f).

This requires storage n⌈log p/ log 2⌉ ∼ log q/ log 2, which is much better than keeping track of tables, which we saw required storage space 2q^{2}(log q)/(log 2)!

Example. For p = 2, n = 3, we have two choices for f: X^{3} +X +1 and X^{3} +X^{2} +1. So one model for 𝔽_{8} is

𝔽_{2}[X]/(X^{3} + X + 1)

and another is

𝔽_{2}[X]/(X^{3} + X^{2} + 1).

This is some of the material covered March 19–21, in Math 195: Cryptography, taught by Hendrik Lenstra, prepared by John Voight jvoight@math.berkeley.edu.

Even though the addition structure is the same in the field, when multiplying we reduce modulo different f. These are, by the theorem, isomorphic as fields, meaning that there is a way of matching up the elements so that the multiplication corresponds.

It suffices to find one such polynomial, therefore. Given a prime number p and a positive integer n, how do we quickly produce a monic irreducible polynomial f ∈ 𝔽_{p}[X] of degree n? Just as in the case of the integers, random searching is enough:

(1) Pick a random f of degree n, monic, in 𝔽_{p}[X].

(2) Test f for irreducibility, and iterate until answer is “yes”.

We need to discuss how fast this algorithm is (what is the analogy of the prime number theorem for 𝔽_{p}[X]?) and give a fast algorithm to test a polynomial for irreducibility.

We let

a_{n}(p) = #{f ∈ 𝔽_{p}[X] : f monic, irreducible, deg f = n}.

The probability of “yes” in (2) above is a_{n}(p)/p^{n}.

From unique factorization in 𝔽_{p}[X] one can dedcue: for all n ≥ 1, ∑_{d|n} da_{d}(p) = p^{n}. From this, we can obtain the closed formula:

a_{n}(p) = \frac{1}{n} ∑_{d|n} μ(d)p^{n/d}

where μ(d) is defined by

μ(d) = \begin{cases}0, & d is divisible by the square of a prime number; \\ (−1)^{r}, & d is the product of r distinct prime numbers. \end{cases}

Example. For example, μ(1) = 1, μ(2) = −1, μ(3) = −1, μ(4) = 0, μ(5) = −1, μ(6) = 1, and so on. Therefore

a_{45}(p) = \frac{1}{45}(p^{45} − p^{15} − p^{9} + p^{3}).

For our purposes, we have the estimate from before:

\frac{p^{n} − 2p^{⌊n/2⌋}}{n} < a_{n}(p) ≤ \frac{p^{n}}{n} .

Therefore

\frac{1}{n} − 2\frac{p^{−n/2}}{n} < \frac{a_{n}(p)}{p^{n}} ≤ \frac{1}{n}.

Hence a_{n}(p)/p^{n} ≈ 1/n. A random polynomial monic of degree n is irreducible with probability ∼ 1/n, independent of p. Recall that a random positive integer near x is prime with probability ∼ 1/ log x: the degree of a polynomial corresponds roughly to the logarithm of an integer.

We have the following remarkable theorem:

Theorem. In 𝔽_{p}[X], one has

X^{p^{n}} − X = ∏_{g∈𝔽_{p}[X] g monic, irreducible (deg g)|n} g

for all n ≥ 1.

Note, the relation

∑_{d|n} da_{d}(p) = p^{n}

expresses that the degrees of the LHS and RHS are the same.

If k is a finite field, #k = q, then we see from the multiplicative structure of k that α^{q} = α. Recall that if k = 𝔽_{p}, where p is prime, then by Fermat’s little theorem, for all a ∈ ℤ, a^{p} ≡ a (mod p). Similarly, we will see that k = 𝔽_{p}[X]/(g), where g is irreducible, with q = p^{deg g}, has the property that for all polynomials f,

f^{p^{deg g}} ≡ f (mod g).

As a consequence, take f = X: then

g | (X^{p^{deg g}} − X).

By induction, we see that α = α^{q} = (α^{q})^{q} = α^{q^{2}} = ⋯ = α^{q^{i}}, so in fact

f^{p^{i deg g}} ≡ f (mod g).

This shows that if deg g | n, then

g | (X^{p^{n}} − X)

in 𝔽_{p}[X].

Now we can prove the theorem:

Proof. Since we have unique factorization in 𝔽_{p}[X], X^{p^{n}} − X can be written as the product of irreducible factors. Therefore for each g which is monic, irreducible, with deg g | n, we know that g | X^{p^{n}} − X, so all of those g occur, hence

X^{p^{n}} − X = h ∏_{\begin{matrix}g \\ deg g|n \end{matrix}} g.

We would like to show that h is trivial.

But from the relation

∑_{d|n} da_{d}(p) = p^{n}

we count degrees on both sides and see that deg h = 0, so h is constant, but since both sides are monic, h = 1. □

Testing for Irreducibility

Given f ∈ 𝔽_{p}[X], monic of degree n ≥ 1, how can we tell whether f is irreducible? We see from the above that one necessary condition is: X^{p^{n}} ≡ X (mod f). This is something that can easily be tested. If no, then the polynomial is not irreducible. If yes, then f | (X^{p^{n}} − X) so f is a subproduct of ∏_{g} g as above so each irreducible factor of f occurs only once in f and has degree dividing n.

We therefore have the following:

Theorem. Let f ∈ 𝔽_{p}[X] be monic of degree n ≥ 1.

(a) Suppose first n is a power of a prime number n = r^{t}, t ≥ 1. Then: f is irreducible if and only if

X^{p^{n}} ≡ X (mod f) and X^{p^{n/r}} = X^{p^{r^{t−1}}} ≢ X (mod f).

(b) For general n: f is irreducible if and only if

X^{p^{n}} ≡ X (mod f)

and for each r | n prime,

X^{p^{n/r}} − X ∈ (𝔽_{p}[X]/(f))^{∗},

i.e. the element X^{p^{n/r}} − X is a unit modulo f.

Proof. It is clear from the above that if f is irreducible, then we have conditions (a) and (b), respectively.

Now suppose that we have the condition in (a). We see that every irreducible factor g must have degree dividing n = r^{t}, so in particular unless g = f its degree must be strictly smaller, hence divide r^{t−1}. Therefore X^{p^{r^{t−1}}} ≡ X (mod f), which is a contradiction.

For (b), let g be an irreducible factor of f. We will show that g = f. Suppose otherwise: then again since deg g | deg f we may assume that there is a prime factor r such that it divides deg f = n to a higher power than deg g; in particular, by adding degrees, we see that X^{p^{n/r}} ≡ X (mod g) and g | f, so g | gcd(X^{p^{n/r}} − X, f) = 1, a contradiction. □

A word on computational complexity: by using repeated squarings as in the case of ℤ/nℤ, we may obtain the time for this algorithm (which requires only powerings and computing gcd) as cn(log p)^{3}. However, if you take advantage of the freshperson’s dream, and use the fact that pth power can be represented as a linear map (and hence a matrix), we can compute this in n(log p) steps: in particular, we see that X^{p^{n}} ≡ X (mod f) if and only if the matrix representing the pth power Frobenius has nth power the identity.

An Aside

We now sketch

∑_{d|n} da_{d}(p) = p^{n}

very briefly! We have the following equalities:

Z(t) = ∑_{\begin{matrix}h∈𝔽_{p}[X] \\ h monic \end{matrix}} t^{deg h} = ∏_{f monic ; irreducible} \frac{1}{1 − t^{deg f}}

= ∑_{n=0}^{∞} p^{n}t^{n} = \frac{1}{1 − pt} = ∏_{d=1}^{∞} \frac{1}{(1 − t^{d})^{a_{d}(p)}} .

Now we apply the logarithmic derivative: to a power series P (t), we have λ(P) = P′/P: we get

λ(1/(1 − pt)) = −λ(1 − pt) = \frac{tp}{1 − tp} = ∑_{n=1}^{∞} p^{n}t^{n}

and this is equal to

λ(∏(1 − t^{d})^{−a_{d}(p)}) = ∑_{d} a_{d}(p)\frac{dt^{d}}{1 − t^{d}} = ∑_{d} ∑_{m=1}^{∞} da_{d}(p)t^{md}.

FINITE FIELDS (CONTINUED): HOW TO CONSTRUCT 5

Now compare coefficients at t^{n}.