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$
12
  • 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$ Commented Jul 4, 2018 at 13:23
  • 1
    $\begingroup$ The fastest method is to ask WA :-) $\endgroup$ Commented Jul 4, 2018 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$ Commented Jul 4, 2018 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$ Commented Jul 4, 2018 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$ Commented Jul 4, 2018 at 15:40

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.