find the inverse of $x^2 + x + 1$ In $\mathbb{F}_2[x]$ modulo $x^4 + x + 1$
find the inverse of $x^2 + x + 1$
not 100% sure but here what i have:
user euclid algorithm:
$x^4 + x + 1 = (x^3 + 1)(x + 1) + x$
$(x^3 + 1) = x * x * x + 1$
$1 = (x^3 + 1) - x * x * x  $
 A: You have a polynomial $\color{blue}{p(x)}$ and you want to find its inverse mod $\color{green}{q(x)}$. We are looking for $a(x)$ and $b(x)$ such that $\color{blue}{p(x)}a(x)+\color{green}{q(x)}b(x)=1$. Because this is the same as saying $\color{blue}{p(x)}a(x)=1$ mod $\color{green}{q(x)}$. The equation $\color{blue}{p(x)}a(x)+\color{green}{q(x)}b(x)=1$ is called Bezout's identity. Well, in place of $1$ you will have the greatest common divisor of $\color{blue}{p(x)}$ and $\color{green}{q(x)}$ in general. This also tells you that the algorithm gives you the existence of the inverse too. If you get a greatest common divisor that is not of degree zero (a constant polynomial) then it doesn't have an inverse.
Euclid's algorithm gives such polynomials $a$ and $b$ if they exist. Then $a(x)$ would be the identity you are looking for.
In our case we get the sequence of divisions:


*

*$\color{green}{x^4+x+1}=\color{blue}{(x^2+x+1)}(x^2+x)+\color{red}{1}$ 

*$\color{blue}{x^2+x+1}=(x^2+x+1)\color{red}{1}+0$ $\longleftarrow$ Yes, from getting remainder $\color{red}{1}$ in the previous division we knew this step was going to be the stopping step.


So, the $\color{red}{1}$ is the greatest common divisor. Because it is $\color{red}{1}$ then we know that $\color{blue}{x^2+x+1}$ does have an inverse and because we have $$\color{blue}{(x^2+x+1)}(x^2+x)+\color{green}{(x^4+x+1)}1=\color{red}{1}$$ we get that $x^2+x$ is that inverse.
A: Since $x^4+x+1$ is irreducible in $\mathbb F_2[x]$, you’re talking about an element of $\mathbb F_{16}$. This is a relatively small finite field, and if you want a relatively quick way of finding reciprocals in such a small field, here’s the method I use:
Find a generator of the multiplicative group, it’s cyclic of order $15$ in this case, and since there are eight generators, you’ll find one fairly quickly. Call the quantity that you’ve found $\rho$. Then write down all the powers of $\rho$, giving you in essence a log table for the multiplicative group. Now once this work is done, you can not only find the reciprocal of anything by inspection, you can find the product of any two things by doing a simple addition and look-up.
A: Using that $\;x^4=x+1\; $ in $\,\Bbb F_2[x]/(x^4+x+1)\;$ , prove that
$$x^2+x=(x^2+x+1)^{-1}\;\;\; (\text{ further hint:}\;(x^2+x+1)^3=1)$$
A: Note that:
$(x^{2}+x+1)(x^{2}+x+1)=x^{2}+x$
$(x^{2}+x)(x^{2}+x+1)=x^{4}+x=1$. To get this I used that $x^{4}+x+1=0$ and that the coefficients are in $\mathbb{F}_{2}$.
So the inverse is $(x^{2}+x+1)^{2}=x^{2}+x$.
