# Fastest way to factorize $x^{18}-x^3$ over $\mathbb{F}_2$

$x^{18}-x^3=x^3(x^{15}+1)=x^3(x^{5\cdot3}+1)=x^3(x^5+1)(x^{10}+x^5+1)$

$x^5+1$ has the root $1$ in $\mathbb{F}_2$ so using the factor theorem I got: $x^5+1=(x+1)(x^4+x^3+x^2+x+1)$ (how to prove that the second factor is irreducible over $\mathbb{F}_2$ ?).

Noticing that the multiplicative order is $4$, so the initial polynomial can be factorized only with polynomials of degree $1$, $2$ and $4$ (the divisors of $4$). Since $0$ and $1$ are not roots of $x^{10}+x^5+1$, its factors has to be of degree $2$ and $4$, the only irreducible polynomial deg $2$ over $\mathbb{F}_2$ is $x^2+x+1$, so dividing $x^{10}+x^5+1$ by it, I got $x^8+x^7+x^5+x^4+x^3+x+1$, which it has to decompose in two degree 4 irreducible polynomials. But this method needs too much time.

Another way is to compute the table of $\mathbb{F}_{16}$ (splitting field of the initial polynomial over $\mathbb{F}_2$), the cyclotomic cosets, etc.

Is there any faster method ?

• The roots of that polynomial are the $5^{th}$ roots of 1. If the polynomial factored into say 2 quadratics, then the splitting field of one of the quadratics would have 4 elements and contain a $5^{th}$ root of 1 which is impossible since the multiplicative group has order 3. – sharding4 Jul 4 '18 at 13:23
• The fastest method is to ask WA :-) – lhf Jul 4 '18 at 13:51
• Because $x^{18}+x^3=x^2(x^{16}+x)$ an even faster way is to search the site we all love. – Jyrki Lahtonen Jul 4 '18 at 14:14
• I see. That's great! For that polynomial we can use the general result that over $\Bbb{F}_p$ we have the factorization (for all $n$) $$x^{p^n}-x=\prod_{q\in\Bbb{F}_p[x], q\ \text{irreducible}, \deg q\mid n}q(x).$$ So in your case of $p=2,n=4$ all the irreducible polynomials of degrees 1,2 or 4 appear as factors with multiplicity one. – Jyrki Lahtonen Jul 4 '18 at 15:34
• For a quartic to be irreducible its constant term must be $1$ (otherwise $x$ is a factor), it must have an odd number of terms (otherwise $1$ is a zero and $x+1$ is a factor), and it must not be the square of the only irreducible quadratic $x^2+x+1$. You already found that the quartic with five terms is irreducible, so that this leaves the quartics with three terms. $x^4$ and $1$ must be in there, so it is just $x^4+x^3+1,x^4+x^2+1$ and $x^4+x+1$. The last bit is that $(x^2+x+1)^2=x^4+x^2+1$ (freshman's dream). The other two are thus irreducible. – Jyrki Lahtonen Jul 4 '18 at 15:40