# Why did they choose $x^4+1$ for the MixColumns step in Rijndael/AES?

In The Design of Rijndael page 39, It describe the design criteria for MixColumns step

1. Dimensions. The transformation is a bricklayer transformation operatingon 4-byte columns.
2. Linearity. The transformation is preferably linear over GF(2).
3. LisDiffusion. The transformation has to have relevant diffusion power.
4. Performance on 8-bit processors. The performance of the transformationon 8-bit processors has to be high.

However, it does not said why choose modulo $x^4+1$ operation in this step. I guess it is becasue it is the simplist polynomial operation otehr than modulo $x^4$, which will cause multiple zeros. I will glad if anyone tell me my guess is wrong.

• I think you mean MixColumns step. Please edit so that other people asking this question in the future can find it. – user47922 May 18 '17 at 22:49
• – Richie Frame May 18 '17 at 23:32
• Yes, it is MixColumns Step. It is a severe typo, thank for correction and thank e-sushi edit this post. – Rikeijin May 19 '17 at 2:14

The idea is that when you're multiplying two four-term (four-byte) polynomials together, you could wind up with a seven-byte polynomial, but you need to reduce it to another four-byte polynomial. They chose $x^4 + 1$ because
$x^i \mod (x^4 + 1) = x^{i \mod 4}$