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

• Find a root of the polynomial in $\mathbb{F}_{16}$ if any. Then the minimal polynomial of this root will be a divisor. – Wuestenfux May 26 '17 at 12:36
• Note that $\mathbb{F}_{16}$ is NOT the ring $\mathbb{Z}/16\mathbb{Z}$. So there is no reason to add something like $16x^5$, as we already have $2x^5 = 0$. You might want to check again if you want to do computations mod 16 or if you want to work with $\mathbb{F}_{16}$... – Dirk May 26 '17 at 12:37
• What tools do you have? I'm not sure you can just factor this polynomial without knowing the proper algorithms, at least not without tons of luck guessing the right coefficients... Furthermore, which representation of $\mathbb{F}_{16}$ do you have, how do your elements look like? – Dirk May 26 '17 at 12:43
• First of all, have you checked that it is the right polynomial ? Then, as @Bemte has asked/remarked, it looks a very difficult queston without having adequate methods/tools. Is it homework ? If yes, what hints has your lecturer given to you ? – Jean Marie May 26 '17 at 20:03
• I once prepared a local copy of field tables of $\Bbb{F}_8$ and $\Bbb{F}_{16}$. The latter may come in handy here for the purposes of checking that $p(X)$ has no zeros in $\Bbb{F}_{16}$. Consequently the cubic factors Jean Marie found are irreducible. Admittedly it may be easier to prove that $p(X)$ is irreducible over $\Bbb{F}_2$, which also, by Galois theory, implies that it is a product of two irreducible cubics over $\Bbb{F}_{16}$. – Jyrki Lahtonen Jun 1 '17 at 9:12

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

• Looks like you lost an $x^2$ and gained an $x$ in the last step of your long equality. – Sean Henderson May 26 '17 at 16:41
• The comment of @Sean Henderson refers to an earlier version that in fact had a flaw. This present solution is completely different. – Jean Marie May 30 '17 at 9:08
• @JeanMarie, I can't see immediately why the constant coefficients in the cubics are $1$. A priori they are $t$, $t^{-1}$ for some $t\in\mathbb{F}_{16}$. Using the Frobenius map shows they must be in $\mathbb{F}_4$ at worst; so you've also got to deal with two (conjugate) cubics whose constants are $\omega$, $\omega^2$ where $\omega^2+\omega+1=0$. – ancientmathematician May 30 '17 at 9:59
• @ancientmathematician In fact, I haven't considered the introduction of this supplementary parameter $t$ because second degree equation $X^2=1$ has $X=\pm 1=1$ as a (unique) solution in GF(16). But I should mention it in my answer. – Jean Marie May 30 '17 at 10:57
• @JeanMarie, the constant terms of the cubics need not be the same, so $x^2=1$ is irrelevant, it's $t_1 t_2=1$ where the $t_i$ are the constant terms. Don't think me rude if I suddenly drop out of sight, I am (British Airways computers willing) about to go on holiday. – ancientmathematician May 30 '17 at 11:09