Division in finite fields

Question

Let's take $GF(2^3)$ as and the irreducible polynomial $p(x) = x^3+x+1$ as an example. This is the multiplication table of the finite field

I can easily do some multiplication such as $$(x^2+x)\cdot(x+1) = x^3 + x^2 + x +1 = x+1+x^2+x+2 = x^2$$

I am wondering how to divide some random fields such as $x^2 / (x+1)$. The result is $x^2+x$ (compare above). But how do I actually calculate this. Polynomial long division does not help be:

1. Why don't I get $x+1$ as result?
2. How can I calculate $x / (x^2+x+1)$? The result should be $x+1$

Answer 1

Hint

You just go the other way around. If $a = bc$ then b and c are on the row and column and a is inside the table. So if $a/c = b$ the same should hold. Now see what c and a and b are for your example and go check in the table.

---

So for example 2) you check which row will give you $x$ inside the table for the column with $x^2+x+1$ on top.

Answer 2

If we have a field $K = F[X]/p(X)$, then we can compute the inverse of $\overline{q(X)}$ in $K$ as follows.

Since $p$ is irreducible, either $q$ is zero in $K$ or $(p,q)=1$. By the Euclidean algorithm, we can find $a,b$ such that $a(X)p(X) + b(X)q(X) = 1$. Then $\overline{b(X)} \cdot \overline{q(X)} = \overline{1}$, so $\overline{b(X)}$ is the inverse of $\overline{q(X)}$.

In your example, the Euclidean algorithm gives us $(x+1)(x^3 + x + 1) + (x^2)(x^2 + x+1) = 1$ (modulo 2), so $(x^2+x+1)^{-1} = x^2$ and $\frac{x}{x^2+x+1} = x(x^2) = x^3 = x+1$.