5
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – sharding4 Jul 4 '18 at 13:23
  • 1
    $\begingroup$ The fastest method is to ask WA :-) $\endgroup$ – lhf Jul 4 '18 at 13:51
  • 2
    $\begingroup$ Because $x^{18}+x^3=x^2(x^{16}+x)$ an even faster way is to search the site we all love. $\endgroup$ – Jyrki Lahtonen Jul 4 '18 at 14:14
  • 2
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Jul 4 '18 at 15:34
  • 2
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Jul 4 '18 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.