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.

  • 1
    $\begingroup$ I think you mean MixColumns step. Please edit so that other people asking this question in the future can find it. $\endgroup$
    – user47922
    May 18, 2017 at 22:49
  • 2
    $\begingroup$ related: crypto.stackexchange.com/questions/15850/… $\endgroup$ May 18, 2017 at 23:32
  • $\begingroup$ Yes, it is MixColumns Step. It is a severe typo, thank for correction and thank e-sushi edit this post. $\endgroup$
    – Rikeijin
    May 19, 2017 at 2:14

1 Answer 1


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}$

See this for an example.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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