<s>[INST] 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$.
 [/INST] 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$.
</s>