You can construct a finite field of order pn for any prime p and positive integer n.
The elements are polynomials modulo an irreducible polynomial of degree n, with coefficients in the integers mod p.
The choice of irreducible polynomial matters, though the fields you get from any two choices will be isomorphic.
For example, the AES encryption algorithm uses the finite field GF(28), i.
e.
the finite field with 28 = 256 elements.
Except we need to be a little careful about saying “the” field.
Since we’re doing concrete calculations, the choice of irreducible polynomial matters, and AES dictates the polynomialx8 + x4 + x3 + x + 1.
How many other irreducible polynomials are there over GF(28) or any other field for that matter?.We’ll assume the leading coefficient is 1, i.
e.
we’ll count monic polynomials, because otherwise we can just divide by the leading coefficient.
The number of monic irreducible polynomials of degree n over a field with q elements is given bywhere μ is the Möbius function and the sum is over all positive integers that divide n.
We can implement this function succinctly in Python.
from sympy import mobius, divisors def I_q(n, q): list = [mobius(d)*q**(n/d) for d in divisors(n)] return sum(list)//n We can compute I_q(8, 2) to find out there are 30 monic irreducible polynomials of degree 8 with coefficients in GF(2), i.
e.
with one-bit coefficients.
There are 256 monic polynomials—the coefficient of xk can be either 0 or 1 for k = 0 … 7—but only 30 of these are irreducible.
Note that in the paragraph above we count the number of monic irreducible polynomials with coefficients in GF(2) that we could use in constructing GF(28).
We haven’t considered how many monic irreducible polynomials there are in GF(28), i.
e.
with coefficients not just in GF(2) but in GF(28).
That would be a much larger number.
If we call I_q(8, 256) we get 2,305,843,008,676,823,040.
.