Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.