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

Joan Daemen and Vincent Rijmen use a representation of GF(2^{8}) where each element is a polynomial of the form *b*_{7}*x*^{7} + *b*_{6}*x*^{6} + *b*_{5}*x*^{5} + *b*_{4}*x*^{4} + *b*_{3}*x*^{3} + *b*_{2}*x*^{2} + *b*_{1}*x* + *b*_{0}, with the *b*_{i} 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 *m* = *x*^{8} + *x*^{4} + *x*^{3} + *x* + 1. Last time we showed that, in GF(2²), *x*^{2} + *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:

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.

As a check, there is an elegant formula for the number of irreducible monic polynomials with coefficients in a finite field:

*N*(*q*, *n*) = (Σ_{d|n} *μ*(*d*) *q*^{n/d})/*n*

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

In particular:

*N*(2, 1) = ((1)2^{1/1})/1 = 2

*N*(2, 2) = ((1)2^{2/1} – (1)2^{2/2})/2 = 1

*N*(2, 3) = ((1)2^{3/1} – (1)2^{3/3})/3 = 2

*N*(2, 4) = ((1)2^{4/1} – (1)2^{4/2} + (0)2^{4/4})/4 = 3

*N*(2, 5) = ((1)2^{5/1} – (1)2^{5/5})/5 = 6

*N*(2, 6) = ((1)2^{6/1} – (1)2^{6/2} – (1)2^{6/3} + (1)2^{6/6})/6 = 9

*N*(2, 7) = ((1)2^{7/1} – (1)2^{7/7})/7 = 18

*N*(2, 8) = ((1)2^{8/1} – (1)2^{8/2} + (0)2^{8/4} + (0)2^{8/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

## 4 thoughts on “Sieving irreducible monic polynomials over a finite field”