Solving quadratic in finite field

Question

Let $x^4+x+1 \in \mathbb{Z}_2 [x]$ which is irreducible. Let $\alpha $ be a root of this polynomial and let $F=\mathbb{Z}_2(\alpha )$.

Let $g= x^2+(\alpha ^3 + \alpha )x+(\alpha^3 +\alpha^2+\alpha) \in F[x]$.

I am asked to find the roots of $g$ in $F$ But how do I do this. I know that $F$ is a field of 16 elements so I could just check all of them but it doesn’t seem in the spirit of the question. Are there any techniques for this?

Answer 1

A trick that can be used here is to use the fact that the polynomial $$L(x):=x^2+(\alpha^3+\alpha)x$$ has the property $$L(x+y)=L(x)+L(y)$$ for all $x,y\in F$. This is because in characteristic two fields we have the rule $(x+y)^2=x^2+y^2$.

So $L(x)$ is a linear transformation (over the prime field $\Bbb{Z}_2$). We can use tools from linear algebra. Let's check what $L$ does to the basis elements: $$ \begin{aligned} L(1)&=\alpha^3+\alpha+1,\\ L(\alpha)&=\alpha^4=\alpha+1,\\ L(\alpha^2)&=\alpha^5+\alpha^4+\alpha^3=\alpha^3+\alpha^2+1,\\ L(\alpha^3)&=\alpha^4=\alpha+1. \end{aligned}. $$ We pretty much see right away that $$L(\alpha+\alpha^2)=L(\alpha^2)+L(\alpha)=\alpha^3+\alpha^2+\alpha$$ (we could also do this with linear algebra and coordinates as was implied in Lonza Leggiera's answer, +1) giving us one root $x_1=\alpha^2+\alpha$.

Obviously $L(\alpha^3+\alpha)=(\alpha^3+\alpha)^2+(\alpha^3+\alpha)^2=0$. Because $L$ is a quadratic, it can have at most two zeros, so the kernel of $L$ is 1-dimensional, spanned by $\alpha^3+\alpha$.

This means that the other solution is $$ x_2=x_1+(\alpha^3+\alpha)=\alpha^3+\alpha^2. $$

Answer 2

Hint

Let $\ x=a_3\alpha^3+a_2\alpha^2+a_1\alpha+a_0\ $, where $\ a_i\in\mathbb{Z}_2\ $. Substituting this value of $\ x\ $ into the equation $\ g(x)=0\ $ and equating coefficients of $\ \alpha^0,\alpha,\alpha^2\ $ and $\ \alpha^3\ $ will give you four linear equations in the four unknowns $\ a_0,a_1,a_2\ $ and $\ a_3\ $. I haven't actually done this myself, but I'm guessing that the coefficient matrix of these linear equations will have rank $\ 3\ $, thus giving you two solutions.