2
$\begingroup$

A skill I'm trying to learn/understand is how to do this manually. I've noticed as a predecessor to a lot of my discrete maths example questions we are asked to obtain the irreducible factorisation of things like $$x^{15}-1, x^{18}-1, x^{20}-1 \in\mathbb{F_2[x]}.$$

What approach should one take generally when trying to do something like this? I've tried practising with smaller ones which are easier to do but I can't really see a general technique.

For $x^{18}-1=(x^9-1)^2=(x^3-1)^2(x^6+x^3+1)^2=(x-1)^2(x^2+x+1)^2(x^6+x^3+1)^2$ This one I mostly understand, aside from the $x^6$ factor, how could you know this was an irreducible polynomial in this field which out memorising them all? Or is that the technique..

Then, for $x^{15}-1$ I am told to assume that the primitive quartic polynomials in $\mathbb{F}_2[x]$ are $x^4+x+1$ and $x^4+x^3+1$.

I can check on wolfram alpha that the factorisation looks like: $x^{15}-1=(x+1)(x^2+x+1)(x^4+x+1)(x^4+x^3+1)(x^4+x^3+x^2+x+1)$

Now my hint suggested there are only $2$ quartic polynomials but this makes use of $3$...unless the $3$rd one is not primitive?

And also, how could one find this factorisation easily by hand? The one above I could attempt trial and error to find the irreducible polynomial of degree $6$ perhaps but for this one that seems a bit strange.

Any advice is greatly appreciated.

$\endgroup$
  • $\begingroup$ Your polynomial $f(x)=x^4+x^3+1$ satisfies $f(x+1)=x^4+x^3+x^2+x+1$. $\endgroup$ – Sungjin Kim May 6 '18 at 0:32
  • 1
    $\begingroup$ That last quartic is not primitive for it is a factor $x^5-1=(x-1)(x^4+x^3+x^2+x+1)$. $\endgroup$ – Jyrki Lahtonen May 6 '18 at 11:31
1
$\begingroup$

Note that from the theory of finite fields,

Theorem

The finite field $\mathbb{F}_{p^n}$ is a splitting field of the polynomial $x^{p^n}-x$.

From this theorem, every element of $\mathbb{F}_{p^n}$ is a root of the polynomial $x^{p^n}-x$. We can apply this to $\mathbb{F}_{2^4}$ and $x^{2^4}-x$.

$$ \begin{align} x^{2^4}-x&=x(x^{15}-1)\\ &=x(x-1)g(x) \end{align} $$ where $g(x)$ contains factors $(x-\alpha)$ for each $\alpha\in\mathbb{F}_{2^4} \backslash \mathbb{F}_2$.

Since $\mathbb{F}_{2^4}$ contains $\mathbb{F}_{2^2}$, we consider an irreducible polynomial of degree $2$ over $\mathbb{F}_2$. Then $$ g(x)=(x^2+x+1)h(x)$$ where $h(x)$ contains factors $(x-\alpha)$ for each $\alpha\in \mathbb{F}_{2^4}\backslash \mathbb{F}_{2^2}$. Each such $\alpha$ must be of degree $4$ over $\mathbb{F}_2$. Thus, $h(x)$ must contain an irreducible polynomial of degree $4$ over $\mathbb{F}_2$. Also, there are exactly three of them, $x^4+x^3+1$, $x^4+x+1$, and $x^4+x^3+x^2+x+1$. This gives the factorization $$ x^{15}-1=(x+1)(x^2+x+1)(x^4+x^3+1)(x^4+x+1)(x^4+x^3+x^2+x+1). $$

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.