Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I know that the AES MixColumn step is calculated as follows

$b(x) = (a(x)c(x)) \mod l(x)$

with $a(x)$ being the column to encode, $c(x)$ the fixed polynomial $c(x) = 3x^3 + x^2 + x + 2$ and $l(x) = x^4+1$ which is reducible over $GF(2^8)$ since $x^4 + 1 = (x+1)^4$.

I wondered about the purpose of the reducibility property of $l(x)$ and so I looked it up in my text book as well as on the internet but I could not find any further explanation on this. As it is my understanding only an irreducible polynomial $f(x)$ would be able to create a field $GF(2^8)[x]/(f(x))$. So my question is:

Is there a particular reason why l(x) must be reducible over $GF(2^8)$ in AES MixColumns?

share|improve this question
up vote 4 down vote accepted

The reason it is not irreducible is because it does not have to be.

For MixColumns, the result must be a polynomial of degree 3 or less, which requires a degree 4 reduction. We are not reducing the elements of the finite field here, but the coefficients of the polynomial generated by multiplication of the fixed and input polynomials. With reduction by $x^4+1$, the reduction can also be represented as replacing the coefficient of $x^0$ with that of $x^4$.

The choice of degree 4 reduction polynomial does not have to be irreducible in $GF(2^8)$ if the fixed polynomial in the matrix multiplication has an inverse, which it does. In the case of $c(x)=3x^3+x^2+x+2$, $c^{-1}(x)=11x^3+13x^2+9x+14$.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.