Multiplicative inverse in the extended euclidean algorithm

Question

I am trying to use the extended euclidean algorithm to find the multiplicative inverse of 02 (in hexadecimal) and $x^8+x^4+x^3+x+1$ over GF($2^8$). I tried to apply the algorithm between $x^2$ and the given polynomial. Dividing the polynomial by $x^2$ gives a quotient of $x^6+x^2+x$ and a remainder of $x+1$ so I tried dividing $x^2$ by the remainder and they are co-prime so the GCD is 1 and according to the algorithm I am using the inverse is the inverse of x+1 modulo $x^2$, for this do I need to apply the extended algorithm again, or how do I proceed?

Answer 1

An easy general way is the forward extended Euclidean algorithm, e.g. see here for a worked example of this method (this is easier and less error-prone than the common "backward" form).

However, in this case it's a bit easier to use an optimization: (inverse $\rm\color{#c00}{reciprocity}$), which computes $\,b \equiv {\large \frac{1}{\color{#c00}{x^2}}}\bmod \color{#c00}f\,$ from $\,a\equiv {\large \frac{1}{\color{#c00}f}} \bmod \color{#c00}{x^2}$ (easier), viz.

suppose $\,af+b\:\!x^2 = 1\,$ and $\,f \equiv 1+x \pmod{\!x^2},\,$ as for your $f = 1+x+x^3+x^4+x^8$.

$\!\!\bmod \color{#0a0}{x^2}\!:\ 1 \equiv af \equiv a(1+x) \iff a \equiv \dfrac{1}{1+x} \equiv \dfrac{\!\!1-x}{1-\color{#0a0}{x^2}} \equiv 1-x$

Thus $\,b = \dfrac{1-af}{x^2},\,$ which yields $\,b =1-x+x^3-x^6+x^7$ for your $f$.

Note $ $ The above method of computing $\,1/(1\!+\!x)\bmod x^2\,$ is not ad-hoc. Rather it is a special case of the method of simpler multiples (a nilpotent analog of rationalizing the denominator).