Counting irreducible polynomials over finite fields

You can construct a finite field of order pⁿ 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(2⁸), i.e. the finite field with 2⁸ = 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 polynomial

x⁸ + x⁴ + x³ + x + 1.

Another example from cryptography is Galois Counter Mode (GCM) which uses the finite field GF(2¹²⁸), specifying the irreducible polynomial

x¹²⁸ + x⁷ + x² + x + 1.

How many other irreducible polynomials are there over GF(2⁸) 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 by

where μ 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)*pow(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 x^k can be either 0 or 1 for k = 0 … 7—but only 30 of these are irreducible. Similarly, there are 2¹²⁸ monic polynomials of degree 128 with binary coefficients, and approximately 2¹²¹ of them are irreducible. Clearly it’s convenient in applications like GCM to use a polynomial of low weight, i.e. one with few non-zero coefficients.

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(2⁸). We haven’t considered how many monic irreducible polynomials there are in GF(2⁸), i.e. with coefficients not just in GF(2) but in GF(2⁸). That would be a much larger number. If we call I_q(8, 256) we get 2,305,843,008,676,823,040.