Finding a polynomial $g$ such that $g^2=f$ for certain $f$ in $\mathbb{F}_{16}$ Let $L = \mathbb{Z}_2[x]/\langle x^4 + x + 1 \rangle$ and $\alpha := [x] \in L$.
I want to find $g \in L[y]$ with  $g^2 = f$ and 
$$f = (\alpha^2 + \alpha)y^8 + \alpha y^4 + \alpha^3y^2 + \alpha + 1 ∈ L[y].$$
My starting point is 
$$ (ay^4+by^2+cy+d)^2= ay^8+b^2y^4+c^2y^2+d^2.$$
From there on I'm trying to find $a,b,c,d \in L$. $d^2 = \alpha +1$ so I'm looking for $f$ with $\alpha + 1 + f = \alpha^4+\alpha+1.$ Hence, $f = \alpha^4$ and $d = \alpha^2$. The same works for $a$ and $b$ but I am stuck with $c$.
For $\alpha^3 + f = \alpha^4 + \alpha +1$, $f$ is $\alpha^4+\alpha^3+\alpha+1$ but I do not know where to go from there because of the the $\alpha^3$ expression.
 A: $c^2=\alpha^3=\alpha^2\alpha=\alpha^2(\alpha^4+1)=\alpha^2(\alpha^2+1)^2=[\alpha(\alpha^2+1)]^2 \Rightarrow c=\alpha(\alpha^2+1).$
A: There a few general tricks that you can use to find square roots in a finite field of characteristic two.


*

*First is to use the Frobenius automorphism $F: t\mapsto t^2$. You know that every element $t\in L$ satisfies the equation $t=t^{16}=F(F(F(F(t))))=\cdots=F(t^8)=(t^8)^2$ Therefore we get that
$$\sqrt t = t^8.$$
Using the Frobenius automorphism was superfluous here, but that's what generalizes to other finite fields, so that's why I wrote it this way. Anyway
$$
\begin{aligned}
c&=\sqrt{\alpha^3}=(\alpha^3)^8=(\alpha^8)^3=((\alpha^4)^2)^3=((\alpha+1)^2)^3\\
&=(\alpha^2+1)^3=\alpha^6+\alpha^4+\alpha^2+1=\alpha^6+\alpha^2+\alpha=
\alpha^2(\alpha^4+1)+\alpha=\alpha^3+\alpha.
\end{aligned}
$$

*Another trick is to use discrete logarithms (in particular if you have a log-table at hand). Here $\alpha$ is a primitive element. Meaning that it is of order $15$. Therefore
$$
\sqrt{\alpha^3}=\sqrt{\alpha^{15+3}}=\sqrt{\alpha^{18}}=\alpha^9=\alpha(\alpha^4)^2=
\alpha(\alpha+1)^2=\alpha^3+\alpha.
$$


Note that in characteristic two the square root is unique, because using a different sign makes no difference.
