Applying Extended Euclidean Algorithm for Galois Field to Find Multiplicative Inverse I was trying to apply the Extended Euclidean Algorithm
for Galois Field. Among the many resources available,
I found the methodology outlined in this document easy to grasp.
The above works fine when applied to numbers.
Now, for $\textit{GF}(2^3)$, if I take the polynomial $x^2$ and
the irreducible polynomial $P(x) = x^3 + x + 1$, I can form the table 
below,
\begin{array}{c|c|c}
\text{Remainder}\ (a)   &        \text{Quotient}\ (q)  &       y\\\hline
x^3 + x + 1 &&                         x^2 + 1\\
x^2& x& x\\
x + 1 &x &1\\
1& x + 1& 0
\end{array}
So, $(x^2)^{-1} \bmod P(x) $ comes out to be $x^2 + 1$. Whereas from other literature I find that the actual result should be, $x^2 + x + 1$.
What is wrong with the calculation I have done?
 A: To calculate the table you have provided, you start with the two given polynomials in the first column, the one with higher order at the top. In this case, $P(x) = x^3 + x + 1$ goes in the first row.
So, for the case you have provided, the table looks like,
\begin{array}{c|c|c}
\text{Remainder}\ (a)   &        \text{Quotient}\ (q)  &       y\\\hline
x^3 + x + 1 &&                     \\
x^2& & \\
\end{array}
As indicated in the document provided, the $a$ and $q$ columns are filled in using the Euclidean algorithm, i.e. by successive division: divide
the next-to-the-last $a$ by the last $a$. The quotient goes into the $q$-column, and the remainder goes into the
$a$-column.
After the $a$ and $q$ columns are filled up, the table will look like,
\begin{array}{c|c|c}
\text{Remainder}\ (a)   &        \text{Quotient}\ (q)  &       y\\\hline
x^3 + x + 1&&\\ 
x^2& x&\\
x + 1& x + 1&\\
1& x + 1
\end{array}
You should remember that all mathematical operations are done over 
$\textit{GF}(2^3)$.
Your mistake was that when you divide $x^2$ by $x+1$, the quotient is $x+1$ and the remainder is $1$. It will be incorrect to take the quotient as $x$ and remainder as $x$. When carrying out a polynomial division, you should remember that: given two univariate polynomials $a$ and $b \not= 0$ defined over a field, there exist two polynomials $q$ (the quotient) and $r$ (the remainder) which satisfy,
$a=bq+r$
and
$\deg(r)<\deg(b)$,
where $\deg(...)$ denotes the degree. Moreover $q$ and $r$ are uniquely defined by these relations. 
Quotient $x$ and remainder $x$ violates the condition, degree of remainder is strictly less than degree of divisor. 
Anyway, coming back to your original problem, the only task remains is to fill up the $y$ column. The $y$-column is filled in from bottom to top. Always start with $0$ for the last $y$ and $1$ for the next-to-
the-last $y$.
Then, working from bottom to top, fill in the $y$’s using the rule,
$(\text{next}\ y) = (\text{last}\ q) \times (\text{last}\ y) + (\text{next-to-last}\ y)$.
So, with the $y$'s filled up, the table becomes,
\begin{array}{c|c|c}
\text{Remainder}\ (a)   &        \text{Quotient}\ (q)  &       y\\\hline
x^3 + x + 1&& x^2 + x + 1\\ 
x^2& x&x + 1\\
x + 1& x + 1&1\\
1& x + 1&0
\end{array}
Again, you should remember that all mathematical operations are done over 
$\textit{GF}(2^3)$.
So, your  inverse of $x^2$ is now given as the topmost $y$ value
that was computed, $x^2 + x + 1$.
Indeed, to  check that $x^2 + x + 1$ is in fact the inverse of $x^2$, where we use the properties
that $x^3 \equiv x + 1 \bmod P(x)$ and $x^4 \equiv x^2 + x \bmod P(x)$:
\begin{align}
(x^2 + x + 1) \cdot x^2 &=& x^4 + x^3 + x^2\\
&\equiv& (x^2 + x) + (x + 1) + x^2 \bmod P(x)\\
&\equiv& 1 \bmod P(x)
\end{align}
