Factoring $x^6 + x^4 + x^3 + x + 1$ over $\mathbb{F}_{16}$

Factor the polynomial $$x^6 + x^4 + x^3 + x + 1$$ over $\mathbb{F}_{16}$.

So far, what I was trying to do is to add some terms which mod under $\mathbb{F}_{16}$: \begin{align} x^6 + x^4 + x^3 + x + 1 &= x^6 + 16x^5 + x^4 + x^3 + 16x^2 + x + 1 \\ &= x^4(x^2 + 16x + 1) + x^2(x + 16x + 1) + 1 \\ &= x^2(x^2 + 1)(x^2 + 16x + 1) + 1 \end{align}

But every time there is a constant in the end. I've tried to express this constant in form of product where one term is the term from first term expansion, but I failed.

Solution 1:

Let $$p(X)=X^6+X^4+X^3+X+1 \ \ \text{with coefficients in GF(16).}$$

Let us first recall that $GF(16)$, like all $GF(2^p)$, is a field of characteristic $2$, thus with $2=0$ and $x+x=0$ for all $x$.

Now, consider the representation of GF(16) that can be found in (https://en.wikipedia.org/wiki/Finite_field#GF.2816.29):

There exist an $\alpha \in $ GF(16) (see remark 2 below) with the following properties

• GF(16)$^*=\langle \alpha \rangle=\{1,\alpha,\alpha^2,\cdots,\alpha^{14}\}$ with $\alpha^{15}=1;$

• it is such that:

$$\tag{*}\alpha^4=\alpha+1.$$

Set $a=\alpha^5$ and $b=a^{-1}=\alpha^{10}.$

Using (*), one can represent $a=\alpha \alpha^4=\alpha^2+\alpha$ and $b=a^2=\alpha^4+\alpha^2=\alpha^2+\alpha+1.$

As a consequence, $a+b=1.$

Then $p(X)$ is factorizable in this way:

$$\tag{1}p(X)=(q(X)+a)(q(X)+b) \ \ \ \ \ \ \ \ \text{where} \ \ \ \ \ \ \ \ q(X):=X^3+X^2+X.$$

Proof of (1) :

Let us expand the RHS of (1):

$q(X)^2+q(X)(a+b)+ab=(X^6+X^4+X^2)+(X^3+X^2+X)+1 \ $ which is equal to $ \ p(X)$.

Remarks :

1) It may be of interest to know that a linear representation of GF(16) by $4 \times 4$ matrices with coefficients in GF(2) is possible, by taking

$$\alpha=\begin{pmatrix}0&0&0&1\\1&0&0&1\\0&1&0&0\\0&0&1&0\end{pmatrix} \ \ \text{giving} \ \ a=\begin{pmatrix}0&0&1&1\\1&0&1&0\\1&1&0&1\\0&1&1&0\end{pmatrix} \ \ \text{and} \ \ b=\begin{pmatrix}1&0&1&1\\1&1&1&0\\1&1&1&1\\0&1&1&1\end{pmatrix}$$

What is the idea behind this association ? The concept of "companion matrix" of a polynomial: $\alpha$ is the companion matrix of polynomial $x^4-x-1$; see (https://en.wikipedia.org/wiki/Companion_matrix) or (https://ucilnica.fri.uni-lj.si/pluginfile.php/14696/mod_folder/content/0/companion_matrix.pdf). In fact, a companion matrix associated to a polynomial has this polynomial as characteristic polynomial; therefore, here, using Cayley-Hamilton theorem, we have: $\alpha^4-\alpha-I_4=0,$ a version of relationship (*).

This representation is especially handy for working with programming languages that have good matrix handling capacities (using Matlab, it is how I have discovered factorization (1)).

2) The fact that the multiplicative group GF(16)$^*$ is cyclic (i.e., generated by a single element) is a classical theorem (Why is the multiplicative group of a finite field cyclic?).

3) I am indebted to @ancientmathematician who has indicated me a flaw in my first reasoning (explaining a certain number of comments that are no longer of interest).