Counting irreducible polynomials over finite fields
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 polynomial
x8 + x4 + x3 + x + 1.
Another example from cryptography is Galois Counter Mode (GCM) which uses the finite field GF(2128), specifying the irreducible polynomial
x128 + x7 + x2 + 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 by
where I1/4 is the Mibius 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. Similarly, there are 2128 monic polynomials of degree 128 with binary coefficients, and 2121 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(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.