How do we reduce the multiplications in the AES mix column layer using $x^4 +1$ I recently learned AES uses $x^4 +1$ to reduce the multiplications in the MixCol layer. However, I used $p(x) = x^8 + x^4 + x^3 + x + 1$ not knowing it was the wrong polynomial and got the correct answer. For example, here is what I did:

\begin{equation*}
\begin{pmatrix}
02 &amp; 03 &amp; 01 &amp; 01 \\
01 &amp; 02 &amp; 03 &amp; 01 \\
01 &amp; 01 &amp; 02 &amp; 03 \\
03 &amp; 01 &amp; 01 &amp; 02
\end{pmatrix}\
\begin{pmatrix}
D4 \\
BF \\
5D \\
30 
\end{pmatrix}
\end{equation*}

If, for example,  we consider the last equation $$03 \cdot D4 \oplus 01 \cdot BF \oplus 01 \cdot 5D \oplus 02 \cdot 30 $$ 
and write it in terms of $x$ 
we get (after cancelling):
$$x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x$$ 
Reducing this using $p(x) = x^8 + x^4 + x^3 + x + 1$ I get: $$x^7 + x^6 + x^5 + x^2 + 1 = E5$$. 

As far as I know this is the correct answer but I did not use $x^4 +1$ at any point. And when I try to reduce $x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x$ using $x^4 + 1$ I get the wrong answer. 


At what point do I use $x^4 + 1$ to reduce the polynomial?
Was my answer just lucky or can we use $p(x) = x^8 + x^4 + x^3 + x + 1$ as I did as an alternative?
The $x^4+1$ is implicit in the matrix.

What you are doing is that you consider formal sums $z_0 + z_1 \alpha + z_2 \alpha^2 + z_3 \alpha^3$ for $z_i$ elements of the field $\mathbb{F}_{256}$, and a formal value $\alpha$ which is not in $\mathbb{F}_{256}$, but is such that $\alpha^4+1 = 0$. You can add and multiply such elements, always keeping the result in the same set by applying the rule that $\alpha^4 + 1 = 0$. If you set:
\begin{eqnarray}
y &amp;=&amp; y_0 + y_1\alpha + y_2\alpha^2 + y_3\alpha^3 \\
z &amp;=&amp; z_0 + z_1\alpha + z_2\alpha^2 + z_3\alpha^3 \\
\end{eqnarray}
then you have:
\begin{eqnarray}
yz &amp;=&amp; (y_0 z_0 + y_1 z_3 + y_2 z_2 + y_3 z_1) \\
&amp;+&amp; (y_0 z_1 + y_1 z_0 + y_2 z_3 + y_3 z_2) \alpha \\
&amp;+&amp; (y_0 z_2 + y_1 z_1 + y_2 z_0 + y_3 z_3) \alpha^2 \\
&amp;+&amp; (y_0 z_3 + y_1 z_2 + y_2 z_1 + y_3 z_0) \alpha^3 \\
\end{eqnarray}

This equation can be expressed as a matrix multiplication. The example in your question really is the multiplication of $z = D4+BF\alpha+5D\alpha^2+30\alpha^3$ by $y = 02+01\alpha+01\alpha^2+03\alpha^3$. By writing it as a multiplication by that specific matrix, you "hide" the polynomial $\alpha^4+1 = 0$ into the matrix (specifically, the matrix columns are $y$, $y\alpha$, $y\alpha^2$ and $y\alpha^3$).

Note: The set of formal sums $z_0 + z_1 \alpha + z_2 \alpha^2 + z_3 \alpha^3$ is actually the ring $\mathbb{F}_{256}[x]/(x^4+1)$, i.e. the ring of polynomials with coefficients in $\mathbb{F}_{256}$ and taken modulo the polynomial $x^4+1$. It shall be noted that this ring is not a field, because $x^4+1$ is not irreducible over $\mathbb{F}_{256}$; indeed, in that field, $x^4+1 = (x+1)^4$ (it's a binary field, addition is XOR, thus $2=0$). The ring not being a field does not prevent the operation from being computed, but it means that there are couple of values $(y,z)$ such that $y\neq 0$, $z\neq 0$, but $yz = 0$. However, the $y$ value used in AES ($02+01\alpha+01\alpha^2+03\alpha^3$) is invertible in that ring, which is a blessing because it means that multiplication by $y$ is a bijection; otherwise, decryption would not always be possible.