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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|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|cite|improve this answer

Your Answer


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.