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?
Best Answer
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}