Affine transformation in AES: Matrix representation I know that the affine transformation of the AES can be represented both as a polynomial evaluation over $\operatorname{GF}(2^8)$ and as a matrix-vector multiplication (see, e.g., p.212 C.4 of The Design of Rijndael for the polynomial representation and p.36 3.9 for the matrix-vector multiplication). I would like to know how this change of representation is done. In other words: given the polynomial representation (or maybe a slightly different polynomial), how can we come up with the matrix-vector representation? Is there some algorithm for this, or is the only way to do it just by "brute-forcing" all possibilites?
In literature there are 2 ways to show the affine transform for a given polynomial, and that depends on the location of the MSB in the input as a polynomial.

The polynomial representation of the full transformation, in the format of the original Rijndael paper, is:

$b(x) = a(x)(x^7 + x^6 + x^5 + x^4 + 1) + (x^7 + x^6 + x^2 + x) ~~mod~~ x^8 + 1$

Where $a(x)$ is the input polynomial, and $(x^7 + x^6 + x^5 + x^4 + 1)$ is the polynomial formula of the affine matrix. $(x^7 + x^6 + x^2 + x)$ is the 'vector' constant.

The original Rijndael paper and Wikipedia use the same representation of the affine transform matrix, so we will start there.

$$
 \begin{bmatrix}
y_0 \\
y_1 \\
y_2 \\
y_3 \\
y_4 \\
y_5 \\
y_6 \\
y_7 \\
 \end{bmatrix}=
 \begin{bmatrix}
1&amp; 0&amp; 0&amp; 0&amp; 1&amp; 1&amp; 1&amp; 1 \\
1&amp; 1&amp; 0&amp; 0&amp; 0&amp; 1&amp; 1&amp; 1 \\
1&amp; 1&amp; 1&amp; 0&amp; 0&amp; 0&amp; 1&amp; 1 \\
1&amp; 1&amp; 1&amp; 1&amp; 0&amp; 0&amp; 0&amp; 1 \\
1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 0&amp; 0&amp; 0 \\
0&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 0&amp; 0 \\
0&amp; 0&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 0 \\
0&amp; 0&amp; 0&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1 \\
 \end{bmatrix}
 \begin{bmatrix}
x_0 \\
x_1 \\
x_2 \\
x_3 \\
x_4 \\
x_5 \\
x_6 \\
x_7 \\
 \end{bmatrix}+
 \begin{bmatrix}
1 \\
1 \\
0 \\
0 \\
0 \\
1 \\
1 \\
0 \\
 \end{bmatrix}$$

The rightmost column of the matrix top to bottom and the top row right to left is the start representation of the affine transform polynomial, the other rows/columns are simply rotations of the polynomial, since it is a rotational matrix. The vector constant top to bottom is the representation of the vector constant polynomial. Note $x_0$ is the LSB of the input.

The other representation is from The Design of Rijndael (page 36), to which you posted a link. You can see the matrix is the same, but rotated 180°. You can also see the input and output have their MSB locations flipped. Make note that addition and XOR in the field are the same.

$$
 \begin{bmatrix}
b_7 \\
b_6 \\
b_5 \\
b_4 \\
b_3 \\
b_2 \\
b_1 \\
b_0 \\
 \end{bmatrix}=
 \begin{bmatrix}
1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 0&amp; 0&amp; 0 \\
0&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 0&amp; 0 \\
0&amp; 0&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 0 \\
0&amp; 0&amp; 0&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1 \\
1&amp; 0&amp; 0&amp; 0&amp; 1&amp; 1&amp; 1&amp; 1 \\
1&amp; 1&amp; 0&amp; 0&amp; 0&amp; 1&amp; 1&amp; 1 \\
1&amp; 1&amp; 1&amp; 0&amp; 0&amp; 0&amp; 1&amp; 1 \\
1&amp; 1&amp; 1&amp; 1&amp; 0&amp; 0&amp; 0&amp; 1 \\
 \end{bmatrix}
 \begin{bmatrix}
a_7 \\
a_6 \\
a_5 \\
a_4 \\
a_3 \\
a_2 \\
a_1 \\
a_0 \\
 \end{bmatrix}+
 \begin{bmatrix}
0 \\
1 \\
1 \\
0 \\
0 \\
0 \\
1 \\
1 \\
 \end{bmatrix}$$

The bottom row of the matrix left to right and the first column bottom to top is the start representation of the affine transform polynomial, the other rows/columns are simply rotations of the polynomial. The vector constant bottom to top is the representation of the vector constant polynomial.