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

I_q(n) = \frac{1}{n} \sum_{d | n} \mu(d) q^{n/d}

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 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 approximately 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.

8 thoughts on “Counting irreducible polynomials over finite fields

  1. HI

    A minor terminology error: ‘ Galois Chaining Mode (GCM)’, is strictly ‘Galois Counter Mode’. The ‘chaining’ being explicit in the use of the counter mode of AES

  2. Thanks, Dave. GCM is an alternative to chaining mode, so that was kind of a bad typo on my part.

  3. I am very interested in this discussion. John you stated that for I_q(128,2) there are 2^121 irreducible polynomials. Is that exact pr approximate? If I apply the formula you provided, I seem to get 2^121 – 2^57. Am I right on the exactly count or am I wrong? This answer is important to me. Thanks.

  4. Anthony, the 2^121 answer is approximate, but I thought it was exact when I first wrote the post. Then I realized I was using ** when I should have been using pow(), and that correction gave me exactly the answer 2^121 – 2^57.

  5. Hi John,
    I would like to compute a polynomial generatorG(x) for the BCH code, so to do that I need to compute the irreducible polynomials first P1, P2, P3, P4,….. It depends on how many bits we want to correct.
    So How can i compute these irreducible polynomials knowing that the N=13 ==> Gf(2^13)= 8192??

    Thanks in advance.

Leave a Reply

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