Irreducibility of $x^4 + x^3 + 1$ over finite field $\mathbb{F}_{2^{a}}$, $1 \leq a \leq 6$

finite-fieldsirreducible-polynomials

I have to discuss the irreducibility of $P(X) = X^4 + X^3 + 1$ over finite field $\mathbb{F}_{2^{a}}$, $1 \leq a \leq 6$.

So, for $a = 1$, we have that $P$ is irreducible since is has no roots in $\mathbb{F}_2$ and not the square of the only irreducible quadratic polynomial over $\mathbb{F}_2$ which is $X^2 + X + 1$

And if $P$ were reducible over $\mathbb{F}_{2^b}$, where $b$ is odd $< 6$, then each of its roots will generate $\mathbb{F}_{2^4}$, but this is a contradiction as $\mathbb{F}_{p^k}$ is a subfield of $\mathbb{F}_{p^k}$ if and only if $k | n$; this is clearly impossible, since $b$ is odd.

Therefore, for $a = 3,5$ i.e. over $\mathbb{F}_{8}$ and $\mathbb{F}_{32}\ P$ is irreducible; and it follows from the above discussion that $P$ is reducible over $\mathbb{F}_{16}$, since a root of this polynomial generates the field.

Now, if we let $\mathbb{F}_4 = \{0,\ 1,\ a,\ a+1\ \vert\ a^2 + a + 1=0\}$ then we see that $P(X) = (X^2 + aX +a)(X^2 + (a+1)X + (a+1))$, hence $P$ is reducible in $\mathbb{F}_4$

Which leaves irreducibility of $P$ over $\mathbb{F}_{64}$. It is here that I'm drawing a blank. Any help is appreciated!

Best Answer

$P$ is reducible over $\mathbb F_{64}$, because reducible over the subfield $\mathbb F_4\subset \mathbb F_{64}$ ($2\mid6$).

Related Solutions

How to Prove Irreducibility of Polynomial Over Finite Field

The test that you're thinking of is Rabin's test for irreducibility, which can be stated as follows.

Let $f(x)$ be a polynomial of degree $n$ over $\mathbb{F}_p$. Then $f$ is irreducible over $\mathbb{F}_p$ if and only if

$f(x)$ divides $x^{p^n}-x$, and

$\mathrm{gcd}\bigl(f(x),x^{p^{n/q}}-x\bigr)=1$ for each prime divisor $q$ of $n$.

For $f(x) = x^{10}+x^3+1 \in \mathbb{F}_2[x]$, we must check that $f(x)$ divides $x^{2^{10}}-x = x^{1024}-x$, and that it is relatively prime with $x^{32}-x$ and $x^4-x$.

For $f(x) = x^5 + x^4+x^3+x^2+x-1 \in\mathbb{F}_3[x]$, we must check that $f(x)$ divides $x^{243}-x$ and that it is relatively prime with $x^3-x$.

All of this is easy to do on a computer. In Mathematica, the PolynomialExtendedGCD command can check polynomial GCD's modulo any prime.

In[1] := PolynomialExtendedGCD[x^10 + x^3 + 1, x^1024 - x, x, Modulus -> 2][[1]]

Out[1] := 1 + x^3 + x^10

In[2] := PolynomialExtendedGCD[x^10 + x^3 + 1, x^32 - x, x, Modulus -> 2][[1]]

Out[2] := 1

In[3] := PolynomialExtendedGCD[x^10 + x^3 + 1, x^4 - x, x, Modulus -> 2][[1]]

Out[3] := 1

This establishes that $x^{10}+x^3+1$ is irreducible over $\mathbb{F}_2$. For the other polynomial, we can try:

In[1] := PolynomialExtendedGCD[x^5+x^4+x^3+x^2+x-1, x^243 - x, x, Modulus -> 3][[1]]

Out[1] := 1

As you can see, the GCD is $1$, so it doesn't divide. Indeed, $$ x^5+x^4+x^3+x^2+x-1 \;=\; \bigl(x^2-x-1\bigr)\bigl(x^3-x^2+x+1\bigr) $$ over $\mathbb{F}_3$, so the second polynomial isn't irreducible.

Edit: As Jyrki Lahtonen and Alex M. point out, one can always just use Mathematica directly to test whether a polynomial is irreducible, so there's not a practical reason to use Rabin's test in Mathematica for these two polynomials. Also, if you have access to a computer, you can always in principle check whether a polynomial is irreducible simply by enumerating all possible factors and then attempting to divide by each factor. If you don't have access to a computer, the methods suggested in their answers are certainly better than doing Rabin's method by hand.

However, Rabin's test is important from an algorithmic point of view as one possible way to check for irreducibility. Indeed, for polynomials of high degree, Rabin's test clearly outperforms trial division by all possible factors, though there are other competitive algorithms. The two given problems are simple enough that almost any algorithm you use on a computer will give the desired results very quickly, but it is still instructive to see how Rabin's test can be applied to these examples.

Related Question