Extended Euclidean Algorithm in $GF(2^8)$? I'm trying to understand how the S-boxes are produced in the AES algorithm. I know it starts by calculating the multiplicative inverse of each polynomial entry in $GF(2^8)$ using the extended euclidean algorithm. However I am having some trouble understanding how to perform the euclidean algorithm with polynomials in a field. Could someone please explain how to do this with a step by step example?

Using Rijndael's finite field, the reducing polynomial is $x^8+x^4+x^3+x+1$.
Suppose we want to compute the inverse of $x^5+1$ in this field. We want to solve the equation
$$
a(x^5+1)+b(x^8+x^4+x^3+x+1)=1
$$
I like to use the Euclid-Wallis Algorithm. Since we are dealing with polynomials, I will write things rotated by $90^\circ$.
$$
\begin{array}{c|c}
x^8+x^4+x^3+x+1&0&1&\\\hline
x^5+1&1&0\\\hline
x^4+x+1&x^3&1&x^3\\\hline
x^2+x+1&x^4+1&x&x\\\hline
\color{#C00000}{1}&\color{#C00000}{x^6+x^5+x^3+x^2+x}&\color{#C00000}{x^3+x^2+1}&x^2+x\\\hline
0&x^8+x^4+x^3+x+1&x^5+1&x^2+x+1
\end{array}
$$
The fifth row tells us that in $\mathbb{Z}_2[x]$
$$
(x^5+1)(\color{#C00000}{x^6+x^5+x^3+x^2+x})+(x^8+x^4+x^3+x+1)(\color{#C00000}{x^3+x^2+1})=\color{#C00000}{1}
$$
Thus, $x^6+x^5+x^3+x^2+x$ is the inverse of $x^5+1$ in $\left.\mathbb{Z}_2[x]\middle/(x^8+x^4+x^3+x+1)\mathbb{Z}_2[x]\right.$.
