4

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?

Anonmath101
  • 1,996
  • 2
  • 13
  • 26
  • 1
    Note that you can't use the quadratic formula as the field has characteristic $2$ – FShrike Dec 10 '22 at 12:31
  • Exactly I started trying this then I realised there was no inverse of 2 so yeah I realise that. – Anonmath101 Dec 10 '22 at 12:34
  • You might try trying to find elements $a,b$ such that $a+b=\alpha^3+\alpha$, $ab=\alpha^3+\alpha^2+\alpha=a+b+\alpha^2$. Test $a,b$ as elements of the form $p+q\alpha+r\alpha^2+s\alpha^3$ where $p,q,r,s\in\{0,1\}$ – FShrike Dec 10 '22 at 12:43

2 Answers2

7

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.

lonza leggiera
  • 25,467
  • 2
  • 9
  • 31
  • I wonder. I noticed that $g(\alpha) = \alpha(\alpha^3 + \alpha^2 + \alpha + 1)$. Is it a coincidence? Also, when write $x$ as a linear combination of the powers of $\alpha$. It seems to me that you are treating $\alpha$ as if it were a primitive element of $\mathbb{Z}_2[\alpha]$. How come you can do that? – Pastudent Dec 10 '22 at 12:48
  • 2
    You don't need $\ \alpha\ $ to be primitive (although it does happen to be so). For *any irreducible* polynomial $\ f\in\mathbb{Z}_2[x]\ $, not necessarily primitive, you have a representation $\ GF(16)\cong$$\,\mathbb{Z}_2[x]/\langle f\rangle\ $, each element of which can be written in the form $\ a_3x^3+a_2x^2+a_1x+a_0\ $. However, since the multiplicative order of $\ \alpha\ $ must divide $15$, and $\ \alpha^5=\alpha^2+\alpha\ne1\ne\alpha^3\ $, $\ \alpha\ $ must, in fact, be primitive. I've no idea whether the relation you noticed is a coincidence or not. – lonza leggiera Dec 10 '22 at 13:20
  • Thank you for giving my brain something to munch on! – Pastudent Dec 10 '22 at 13:22
7

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

Jyrki Lahtonen
  • 128,025
  • 25
  • 261
  • 637
  • When the field is a bit larger, and we cannot simple spot the solution from a list of images of basis elements, we can [first use a trace test for solvability, and then the so called *half-trace* (as a substitute for square roots) to actually find the roots](https://math.stackexchange.com/a/4392472/11619). The catch is that the half-trace has that simple form only when we work in a field with $2^m$ elements and $m$ is **odd**. In finite fields with $p^n$ elements, $p$ an odd prime, we can use the normal quadratic formula, but finding the square root may be a bit taxing. – Jyrki Lahtonen Dec 10 '22 at 13:21
  • There's also the [Cantor-Zassenhaus](https://en.wikipedia.org/wiki/Cantor–Zassenhaus_algorithm) and [Berlekamp](https://en.wikipedia.org/wiki/Berlekamp's_algorithm) algorithms, which will work over any finite field. – lonza leggiera Dec 10 '22 at 23:14
  • Correct @lonzaleggiera. And any degree polynomial. See [this old answer of mine](https://math.stackexchange.com/a/893882/11619) for an annotated example run of Cantor-Zassenhaus in a small case. – Jyrki Lahtonen Dec 11 '22 at 05:31