I am working on finding the multiplicative reverse in $GF(2^8)$ using the Euclidean Algorithm but after reading multiple sources, I feel as though I am proceeding incorrectly. Using the irreducible polynomial $m(p)=x^8+x^4+x^3+x+1=0x11B$ I am trying to find the inverse of $x^6+x^4+x+1=0x53$
I know using long division (via http://www.wolframalpha.com/widgets/view.jsp?id=f396eaca9aaccbf858652bccc972324a) I get for the first step
$$(x^8+x^4+x^3+x+1)=(x^6+x^4+x+1)*(x^2-1)+(2x^4-x^2+2x+2)$$
but do I keep the negatives and even coefficients? I can't seem to get a reasonable answer and all the examples I have seen use simpler numbers. I know the answer to be $x^7+x^6+x^3+x=0xCA$ I just cannot seem to get there.
Best Answer
Here are the steps you should obtain.
\begin{align} &x^8+x^4+x^3+x+1 = (x^6+x^4+x_1+1) (x^2 + 1) + x^2\\ &x^6+x^4+x+1 = x^2 (x^4 + x^2) + x + 1\\ &x^2 = (x+1) x + 1. \end{align}