How to calculate multiplicative inverses in $GF(2^3)$ without the Euclidean algorithm

Question

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$.

Answer 1

$\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. $$

Answer 2

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$.