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