Matthew van Eerde's web log
I am a Software Development Engineer in Test working for the Windows Sound team. You can contact me via email: mateer at microsoft dot com
Friend key: 28904932216450_59cd9d55374be03d8167d37c8ff4196b
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 m = x8 + 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:
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) qn/d)/n
where μ(x) is the Möbius function.
N(2, 1) = ((1)21/1)/1 = 2 N(2, 2) = ((1)22/1 - (1)22/2)/2 = 1N(2, 3) = ((1)23/1 - (1)23/3)/3 = 2N(2, 4) = ((1)24/1 - (1)24/2 + (0)24/4)/4 = 3N(2, 5) = ((1)25/1 - (1)25/5)/5 = 6N(2, 6) = ((1)26/1 - (1)26/2 - (1)26/3 + (1)26/6)/6 = 9N(2, 7) = ((1)27/1 - (1)27/7)/7 = 18N(2, 8) = ((1)28/1 - (1)28/2 + (0)28/4 + (0)28/8)/8 = 30
This checks out with the script.
The script is a little naïve about how it multiplies coefficients, so it only works for prime q.