3
$\begingroup$

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.

2 Answers 2

2

$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).$

2

There a few general tricks that you can use to find square roots in a finite field of characteristic two.

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

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