# Sieving irreducible monic polynomials over a finite field

Last time we talked about the addition and multiplication tables for GF(2²); GF(28) is relevant for the Rijndael encryption scheme.

Joan Daemen and Vincent Rijmen use a representation of GF(28) where each element is a polynomial of the form b7x7 + b6x6 + b5x5 + b4x4 + b3x3 + b2x2 + b1x + b0, with the bi being bits. A polynomial is represented by a single byte. Addition is component-wise (modulo 2); two polynomials can be added with a single XOR operation. Multiplication is a little more complicated.

Rijndael defines multiplication as normal polynomial multiplication, followed by taking a modulus using the reduction polynomial mx8 + x4 + x3 + x + 1. Last time we showed that, in GF(2²), x2 + x + 1 was used to reduce polynomial multiplication, and also that a necessary quality for a reduction polynomial is that it be irreducible/prime.

Last time I hinted at the question: how do we show that m is irreducible? Well, one way is to do trial division of all polynomials up to degree 4.

But that’s no fun. Instead, let’s write a script to generate all irreducible polynomials, and see if m is on it! The approach is very similar to the Sieve of Eratosthenes: generate a list of all the polynomials, then traverse it from the low end to the high end; circle each element that hasn’t been crossed out, then cross out all multiples of that element.

The first argument q is the modulus of the coefficients (in this case, 2) and the second argument d (in this case, 8) is how high the degree can go. Here is the output of the script:

>perl polynomial-sieve.pl 2 8
Finding monic irreducible polynomials of degree up to 8 and coefficients mod 2
Generating all monic polynomials…
Sieving out all reducible polynomials…
1
x
x + 1
x^2 + x + 1
x^3 + x + 1
x^3 + x^2 + 1
x^4 + x + 1
x^4 + x^3 + 1
x^4 + x^3 + x^2 + x + 1
x^5 + x^2 + 1
x^5 + x^3 + 1
x^5 + x^3 + x^2 + x + 1
x^5 + x^4 + x^2 + x + 1
x^5 + x^4 + x^3 + x + 1
x^5 + x^4 + x^3 + x^2 + 1
x^6 + x + 1
x^6 + x^3 + 1
x^6 + x^4 + x^2 + x + 1
x^6 + x^4 + x^3 + x + 1
x^6 + x^5 + 1
x^6 + x^5 + x^2 + x + 1
x^6 + x^5 + x^3 + x^2 + 1
x^6 + x^5 + x^4 + x + 1
x^6 + x^5 + x^4 + x^2 + 1
x^7 + x + 1
x^7 + x^3 + 1
x^7 + x^3 + x^2 + x + 1
x^7 + x^4 + 1
x^7 + x^4 + x^3 + x^2 + 1
x^7 + x^5 + x^2 + x + 1
x^7 + x^5 + x^3 + x + 1
x^7 + x^5 + x^4 + x^3 + 1
x^7 + x^5 + x^4 + x^3 + x^2 + x + 1
x^7 + x^6 + 1
x^7 + x^6 + x^3 + x + 1
x^7 + x^6 + x^4 + x + 1
x^7 + x^6 + x^4 + x^2 + 1
x^7 + x^6 + x^5 + x^2 + 1
x^7 + x^6 + x^5 + x^3 + x^2 + x + 1
x^7 + x^6 + x^5 + x^4 + 1
x^7 + x^6 + x^5 + x^4 + x^2 + x + 1
x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + 1
x^8 + x^4 + x^3 + x + 1
x^8 + x^4 + x^3 + x^2 + 1
x^8 + x^5 + x^3 + x + 1
x^8 + x^5 + x^3 + x^2 + 1
x^8 + x^5 + x^4 + x^3 + 1
x^8 + x^5 + x^4 + x^3 + x^2 + x + 1
x^8 + x^6 + x^3 + x^2 + 1
x^8 + x^6 + x^4 + x^3 + x^2 + x + 1
x^8 + x^6 + x^5 + x + 1
x^8 + x^6 + x^5 + x^2 + 1
x^8 + x^6 + x^5 + x^3 + 1
x^8 + x^6 + x^5 + x^4 + 1
x^8 + x^6 + x^5 + x^4 + x^2 + x + 1
x^8 + x^6 + x^5 + x^4 + x^3 + x + 1
x^8 + x^7 + x^2 + x + 1
x^8 + x^7 + x^3 + x + 1
x^8 + x^7 + x^3 + x^2 + 1
x^8 + x^7 + x^4 + x^3 + x^2 + x + 1
x^8 + x^7 + x^5 + x + 1
x^8 + x^7 + x^5 + x^3 + 1
x^8 + x^7 + x^5 + x^4 + 1
x^8 + x^7 + x^5 + x^4 + x^3 + x^2 + 1
x^8 + x^7 + x^6 + x + 1
x^8 + x^7 + x^6 + x^3 + x^2 + x + 1
x^8 + x^7 + x^6 + x^4 + x^2 + x + 1
x^8 + x^7 + x^6 + x^4 + x^3 + x^2 + 1
x^8 + x^7 + x^6 + x^5 + x^2 + x + 1
x^8 + x^7 + x^6 + x^5 + x^4 + x + 1
x^8 + x^7 + x^6 + x^5 + x^4 + x^2 + 1
x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + 1
Done!

Note that m is not just prime, it is the lowest of the monic 8-degree polynomials with coefficients mod 2.

The script itself (in Perl) is attached. It makes no claims to being pretty or efficient.

N(q, n) = (Σd|n μ(d) qn/d)/n

where μ(x) is the Möbius function.

In particular:

N(2, 1) = ((1)21/1)/1 = 2
N(2, 2) = ((1)22/1 – (1)22/2)/2 = 1
N(2, 3) = ((1)23/1 – (1)23/3)/3 = 2
N(2, 4) = ((1)24/1 – (1)24/2 + (0)24/4)/4 = 3
N(2, 5) = ((1)25/1 – (1)25/5)/5 = 6
N(2, 6) = ((1)26/1 – (1)26/2 – (1)26/3 + (1)26/6)/6 = 9
N(2, 7) = ((1)27/1 – (1)27/7)/7 = 18
N(2, 8) = ((1)28/1 – (1)28/2 + (0)28/4 + (0)28/8)/8 = 30

This checks out with the script.

EDIT 2015-10-31: move script to https://github.com/mvaneerde/blog/blob/master/rijndael/polynomial-sieve.pl