How to calculate multiplicative inverses in $GF(2^3)$ without the Euclidean algorithm The problem I have concerns finite field arithmetic in $GF(p^k)$.
I know how to find multiplicative inverses using the extended Euclidean algorithm, but for my exams I need to calculate multiplicative inverses in $GF(2^3)$ without it.
What's the best way to do this? Is there even a convenient way?
The irreducible polynomial I have is $x^3 + x + 1$.
 A: As an alternative, build the table of the so called discrete logarithm. Let $a$ be a root of $f = x^{3} + x + 1$. Then
\begin{align}
&a^{0} = 1\\
&a^{1} = a\\
&a^{2} = a^{2}\\
&a^{3} = a + 1\\
&a^{4} = a^{2} + a\\
&a^{5} = a^{2} + a + 1\\
&a^{6} = a^{2} + 1\\
&a^{7} = 1\\
\end{align}
So to compute the inverse of $a^{2} + a$, say, you note that $a^{2} + a = a^{4}$. Since $a^{7} = 1$, the inverse of $a^{4}$ is $a^{3} = a + 1$. 
Note that in building the table you are doing Euclidean divisions in a simplified form. For instance
$$
a^{5} = a^{4} a = (a^{2} + a) a = a^{3} + a^{2} = a + 1 + a^{2}
$$
since $a$ is a root of $x^{3} + x + 1$, and thus $a^{3} = a + 1$.
A: $\mathbb{F}_2$ is a pretty small base field, so to find the inverse of an element in $\mathbb{F}_2/(x^3+x+1)=\mathbb{F}_8$ is always really simple. For instance, let us find the inverse of $x^2+x$. For any $a,b,c\in\mathbb{F}_2$
$$ (x^2+x)(ax^2+bx+c) = (c+b-a)x^2+(c-b)x+(a+b) $$
holds in $\mathbb{F}_2/(x^3+x+1)$, so the inverse of $x^2+x$ can be found by solving $c+b-a=0, c-b=0, a+b=1$ in $\mathbb{F}_2$, leading to $a=0$ and $b=c=1$.
Double-check:
$$ (x+1)(x^2+x) = x^3+x^2+x^2+x = x^3+x = 2x+1 = 1. $$
