<s>[INST] Let $K=\mathbb{Z}_2[x]/\langle x^4+x^2+x \rangle$ Find a $g\in K$ such that $g^2=x^3+x+1$ Let $K=\mathbb{Z}_2[x]/\langle x^4+x^2+x \rangle$. Find a $g\in K$ such that $g^2=x^3+x+1.$
I tried $x^3+x+1$ itself but unfortunately the degree is only $2$. I don't know how I can multiply something and get a polynomial of degree $3$.
 [/INST] A nice trick to know.
$\newcommand{\d}{\frac{\mathbb Z_2[x]}{\langle x^4+x^2+x\rangle}}$In $\mathbb Z_2[x]$, we have the nice identity that $(a+b)^2 = a^2+2ab+b^2 = a^2+b^2$, because $2ab \equiv 0$ in $\mathbb Z_2[x]$! This naturally becomes $(a+b+c)^2 = a^2+b^2+c^2$ in $\mathbb Z_2[x]$ as well.
We can use this to great advantage as follows : let $p$ be an element satisfying $p^2 = x$ in the ring $\d$. Then $(p^3)^2 = x^3$ and $1^2 = 1$ therefore $(p^3+p+1)^2 = p^6+p^2+1 = x^3+x+1$ in $\d$.
So let's search for such a $p$ : $p^2 = x + h(x)(x^4+x^2+x)$ for some polynomial $h \in \mathbb Z_2[x]$. We start with the simplest $h$ (note $h = 0$ is not useful) , i.e. $h \equiv 1$. For this , we get the RHS as $$x^4+x^2+2x = x^4+x^2 = x^2(x^2+1) = x^2(x+1)^2 = [x(x+1)]^2$$
(The step $x^2+1 = (x+1)^2$ follows from the same $\mathbb Z_2$ identity I discussed earlier)
Et voilà! So $p = x(x+1)$, and $p^3+p+1$ provides the required square root.

Confirmation :
$$
p^3+p+1 = x^3(x+1)^3 + x(x+1)+1 = x^6 + x^5+x^4+x^3+x^2+x+1
$$
modulo $x^4+x^2 + x$ this reduces to $x^3+x+1$, whose square is in fact $(x^3+x+1)^2 = x^3+x+1$.
</s>