# 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.

-

$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).$
1. 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}
2. 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.$$