Find inverse of element in a binary field

The question states:

Let us consider the field $GF(2^4)$ with multiplication modulo $x^4+ x^3+1$

Find all y such that $1010(y + 0011) = 1111$, in other words find y that satisfies $(x^3+x)(y +x+1) = x^3+x^2+x+1$

I tried to find the inverse for element $1010$ to multiply both sides of the equation and continue from there, I tried by solving the equation:

$(x^3+x)(ax^3+bx^2+cx+d) = 1$

But the solution I get is that $a=0,b=1,c=1,d=0$ which doesn't produce the inverse element.

What is the inverse element of $(1010)$ in this field and how can I arrive at that solution?

Any help is greatly appreciated.

Solution 1:

We know $$x^4+x^3+1=0 .\tag1$$ It will be useful to know $$ x^4 = x^3+1\tag2$$ $$ x^5 = x^4+x=(x^3+1)+x = x^3+x+1\tag3$$ $$ x^6 = x^5+x^2 = (x^3+x+1)+x^2 = x^3+x^2+x+1\tag4 $$ These will be useful for doing a calculation like $(x^3+x)(ax^3+bx^2+cx+d) = 1$ that the OP proposes.

Compute \begin{align} 1 &= (x^3+x)(ax^3+bx^2+cx+d) \\ &=(a)x^6+(b)x^5+(c+a)x^4+(d+b)x^3+(c)x^2+(d)x+0 \\ &=(a+b+d+c+a+b)x^3+(a+c)x^2+(a+b+d)x+(a+b+c+a) \\ &=(d+c)x^3+(a+c)x^2+(a+b+d)x+(b+c) \end{align} Thus \begin{align} d+c&=0\\a+c&=0\\a+b+d&=0\\b+c&=1 \end{align} So $d=c$, then $a=c$, then $b=a+d=c+c=0$, then $c=d=a=1$. So $$ (x^3+x)^{-1} = x^3+x+1 $$

Solution 2:

Here are some methods to compute this using a computer. The software is sagemath.

First, if the program supports defining finite fields with a given polynomial, you can just use that:

K.<a> = GF(2^4, modulus=x^4 + x^3 + 1)
(a^3 + a)^-1
  => a^3 + a + 1

You can also use the extended GCD which gives polynomials $u, v$ such that $uf + vg = 1$ so, modulo $f$, that gives $v = g^{-1}$.

K = GF(2)[x]
xgcd(K(x^4 + x^3 + 1), K(x^3 + x)) # K(...) means "as an element of K"
  => (1, x^2 + x + 1, x^3 + x + 1)

So $(x^3 + x + 1)(x^4 + x^3 + 1) + (x^3 + x + 1)(x^3 + x) = 1$.

You can also do it "by hand" using companion matrices. If $x^4 + ax^3 + bx^2 + cx + d$ is the minimal polynomial of your generator $\alpha$, then form the matrix

$$A = \begin{pmatrix} 0 & 0 & 0 & -d \\ 1 & 0 & 0 & -c \\ 0 & 1 & 0 & -b \\ 0 & 0 & 1 & -a \end{pmatrix}$$

In this way, $A$ also has that minimal polynomial. More specifically, each column represents $\alpha \cdot t$ for $t \in \{1, \alpha, \alpha^2, \alpha^3\}$. Now you can compute $(A^3 + A)^{-1}$, and again the columns represent $(\alpha^3 + \alpha)^{-1} \cdot t$ for $t$ in that ordered basis. Of course, you want $t = 1$ to find $(\alpha^3 + \alpha)^{-1}$.

Here $(a,b,c,d) = (1,0,0,1)$ and

$$(A^3 + A)^{-1} = \begin{pmatrix} 1&1&1&0\\ 1&1&1&1\\ 0&1&1&1\\ 1&1&0&1 \end{pmatrix}.$$

Thus $(\alpha^3 + \alpha)^{-1} = 1 + \alpha + \alpha^3$ by reading the first column.

You can also just solve the linear system $(A^3 + A)u = (1,0,0,0)$ rather than the full inverse $(A^3 + A)U = I$. This works out to be the same linear system as given in GEdgar's answer.

Solution 3:

You can use the Extended Euclidean algorithm to find the inverse of $x^3+x$ modulo $x^4+ x^3+1$ in $GF(2)[x]$

Given $a$ and $b$ you will find $u$ and $v$ such that $$au+bv=\gcd(a,b)$$ in our example $\gcd(a,b)=1$ because $a$ is an irreducible polynomial and $\deg(a)>\deg(b)$. So we have $$bv\equiv 1\pmod(a)$$ and $v$ is the multiplicative inverse.

We have to do some polynomial long divisions to find the greatest common divisor. From these divisions we can construct the representation of the greatest common divisor.

(x^4+ x^3+1) : (x^3+x) = x+1
 x^4     +^2
------------
x^3 + x^2 +1
x^3 + x
------------
x^2+x+1

so we have

$$ x^4+ x^3+1=(x^3+x) ( x+1)+ x^2+x+1$$ and further $$x^2+x+1=(x^4+ x^3+1) + (x^3+x) ( x+1)$$ we continue this process and get

(x^3+x) : (x^2+x+1) = x + 1
 x^3+x^2+x
----------
x^2
x^2+x+1
-------
    x+1

$$ (x^3+x) = (x^2+x+1)(x+1) +(x+1) $$

$$x+1 = (x^3+x) + (x^2+x+1)(x+1)$$

x^2+x+1 : x+1 = x
x^2+x
-------
      1

$$x^2+x+1 =( x+1 )x +1$$ and so, by substituting the previous results $$1= (x^2+x+1) +( x+1 )x \\ = (x^2+x+1)+ ( (x^3+x) + (x^2+x+1)(x+1))x\\ =(x^2+x+1)(x^2+x+1)+(x^3+x)x\\ =((x^4+ x^3+1) + (x^3+x) ( x+1))(x^2+x+1)+(x^3+x)x\\ =(x^4+ x^3+1)(x^2+x+1) + (x^3+x)(( x+1))(x^2+x+1)+x)\\ =(x^4+ x^3+1)( x^2+x+1)+ (x^3+x)(x^3+x+1)$$

So $$(x^3+x)(x^3+x+1)=1 \pmod{x^4+ x^3+1}$$

and the inverse of $1010$ in $GF(2^4)$ is $1011$.

Another way to calculate the inverse, at least for such small fields, to use the fact that

$$r\cdot r^{\text{ord} (r) -1}\equiv r^{\text{ord}( r)} \equiv 1$$ in a field. $\text{ord}(r)$ is a divisor of the order of the multiplicative group of the field. In our case this means $$\text{ord}(x^3+x) \in \{3,5,15\}$$ and so $$(x^3+x)^{-1} in \{(x^3+x)^2, (x^3+x)^4, (x^3+x)^{14}\}$$

So first we calculate $$(x^3+x)^2=x^6+x^2=x^3+x+1$$ and further $$(x^3+x)^3=(x^3+x+1)(x^3+x)=1$$ and we have found the inverse $x^3+x+1$