How can I prove irreducibility of polynomial over a finite field?

Solution 1:

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.

Solution 2:

Neither polynomial has zeros in the respective prime field, so they do not have linear factors either.

Let's check the first polynomial $p(x)=x^{10}+x^3+1\in\Bbb{F}_2[x]$. The claim is that it is irreducible. A more efficient way of using the cited result is to observe that if $p(x)$ were a product of two or more irreducible factors at least one of those factors would have degree $\le5$. We eliminate these possibilities one-by-one. Testing for the presence of higher degree factors becomes progressively a little bit harder as the degree goes up, but the principle is always the same, and this result gives us a tool.

Could it have an irreducible quadratic factor? By the cited result all the irreducible quadratic polynomials are factors of $p_2(x):=x^{2^2-1}-1=x^3+1$. To eliminate the possibility of $p(x)$ having a quadratic factor it thus suffices to show that $\gcd(p(x),p_2(x))=1$. Because $p(x)-p_2(x)=x^{10}$ any common factor they have is also a factor of $x^{10}$, but the only irreducible factor of $x^{10}$ is $x$, so we have cleared this obstacle.

To eliminate the possibility of $p(x)$ having a cubic factor it similarly suffices to check that $\gcd(p(x),p_3(x))=1$, where $p_3(x)=x^{2^3-1}-1=x^7+1$. Here we see (the first step in calculating this gcd by Euclid's algorithm) that $$ p(x)-x^3p_3(x)=1, $$ so no common factors there either.

To eliminate the possibility of a quartic factor of $p(x)$, we need to calculate $\gcd(p(x),p_4(x))$ with $p_4(x)=x^{2^4-1}-1=x^{15}+1.$ Let's run Euclid: $$ \begin{aligned} p_4(x)-x^5p(x)&=x^8+x^5+1=: r_1(x)\\ p(x)-x^2r_1(x)&=x^7+x^3+x^2+1=:r_2(x). \end{aligned} $$ Here we could continue with Euclid, but we can also save a step or two by factoring the remainder whenever we can do so easily. Here $$ r_2(x)=x^3(x^4+1)+(x^2+1)=x^3(x^2+1)^2+(x^2+1)=(x^2+1)(x^5+x^3+1). $$ We know from earlier steps that $p(x)$ is not divisible by $(x+1)$. Because $(x^2+1)=(x+1)^2$, we can discard that factor as a possibility, and continue Euclid with $\gcd(r_1(x), r_3(x))$ where $r_3(x)=x^5+x^3+1$. We see that $$ \begin{aligned} r_1(x)-x^3r_3(x)&=x^6+x^5+x^3+1=(x+1)(x^5+x^2+x+1)\\ &=(x+1)^2(x^4+x^3+x^2+1)=(x+1)^3(x^3+x+1). \end{aligned} $$ Here I used extensively the trick (based on geometric sums) that whenever $0<a<b$ we have $$ \frac{x^a+x^b}{x+1}=x^a+x^{a+1}+x^{a+2}+\cdots+x^{b-1}. $$ Anyway, the above calculation shows that any eventual common factor of $p(x)$ and $p_4(x)$ is also a factor of the cubic $x^3+x+1$, but we already showed that $p(x)$ has no cubic factors. Therefore we are done with this case, too.

The last step of proving that $p(x)$ as no quintic factors needs another run of Euclid. This time checking that $\gcd(p(x),p_5(x))=1$, where $p_5(x)=x^{31}+1$. To get started we use square-and-multiply. We already calculated in the previous step that $$ x^{15}\equiv x^8+x^5\pmod{p(x)}.\qquad(*) $$ Consequently $x^{16}\equiv x^9+x^6\pmod{p(x)}$. Squaring $(*)$ (Freshman's dream simplifies squaring in characteristic two) gives $$ x^{30}\equiv x^{16}+x^{10}\equiv (x^9+x^6)+x^{10}\pmod{p(x)}. $$ Here $$ x^{10}+x^9+x^6-p(x)=x^9+x^6+x^3+1. $$ Therefore (multiply by $x$) $$ x^{31}\equiv x^{10}+x^7+x^4+x\equiv x^7+x^4+x^3+x+1\pmod{p(x)}. $$ So we know the remainder of $p_5(x)$ modulo $p(x)$. The remaining task is thus to check that $$ \gcd(p(x),x^7+x^4+x^3+x)=1. $$ Leaving that to you :-)

Your other polynomial $$ q(x)=x^5+x^4+x^3+x^2+x-1\in\Bbb{F}_3(x) $$ is quintic. So if it is reducible, it must have one factor that is either linear or a quadratic. We eliminated the possibility of linear factors by checking that it has no zeros. Using the above technique we find eventual quadratic factors by calculating $$ \gcd(q(x),q_2(x))\in\Bbb{F}_3[x]. $$ Here $q_2(x)=x^{3^2-1}-1=x^8-1$. Leaving it to you to run this instance of Euclid, and find the quadratic factor.

Solution 3:

I think that the criterion that you allude to is the following:

Assume that $X^p - a$ has no roots in $\Bbb F _{p^n}$. Then $X^{p^m} - a$ is irreducible in $\Bbb F _{p^n}[X]$ $\forall m \ge 1$.

In any case, you can't use it here.

1) Let us see how to prove that the second polynomial (call it $P$) is reducible. First, none of $0, 1, 2$ is a root, so $P$ has no factor of degree $1$ (and, therefore, no factor of degree $4$). Let us see whether $P$ can be written as a product of two polynomials, of degree $2$ and, respectively, $3$. The long method is to multiply the polynomials $aX^2 + bX + c$ and $eX^3 + fX^2 + gX + h$, equate the coefficients of equal powers etc...

A shorter approach is the following: let us list all the polynomials of degree $2$ and check whether they divide $P$. Since $P$ has no linear factor, it is enough to list only those polynomials of degree $2$ that are irreducible. Note that no such polynomial may end in $0$, so the constant term is $1$ or $2$. Concerning the leading coefficient, it is enough to consider only monic polynomials. So far we get the polynomials $X^2 + aX + 1$, $X^2 + aX +2$. A polynomial of degree $2$ is irreducible if it has no roots, i.e. if its discriminant is not a perfect square. Since the only perfect squares in $\Bbb F _3$ are $0$ and $1$, you want $a$ such that the discriminant should be $2$.

In the first case, the discriminant is $a^2 - 4$, so you want $a$ such that $a^2 - 4 = 2$, so $a=0$.

In the second case, the discriminant is $a^2 - 8$, so you want $a$ such that $a^2 - 8 = 2$, i.e. $a^2 = 1$, i.e. $a=1$ or $a=2$.

So, the only monic irreducible polynomials of degree $2$ are $X^2 + 1$, $X^2 + X + 2$, $X^2 + 2X +2$. Let us see which one divides our polynomial.

Note that $P = X^3 (X^2+1) + X^2 (X^2+1) + X-1$, so when you divide $P$ by $X^2 +1$ you get the remainder $X-1$, so $X^2-1 \not| P$.

Finally, try to divide $P$ by the last two polynomials. $X^2 + 2X +2$ will turn out to be a factor.

2) Concerning the first polynomial (call it $Q$), the approach will be similar. First, note that it has no roots, so it has no linear factor. Therefore, we are going to look only for irreducible factors of degree $2, \dots, 5$. In order to be irreducible, these potential factors must have the constant term $1$.

Looking for irreducible polynomials of degree $2$, these must look like $X^2 +aX +1$. Clearly, $a=1$ gives the only irreducible one.

For degree $3$, you want those polynomials $X^3 + aX^2 + bX +1$ that have no linear factor; since $0$ cannot be a root, you also do not want $1$ to be so, therefore you want $1+a+b+1 \ne 0$, which means $a+b =1$, so the only possibilities are $X^3 + X^2 +1$ and $X^3 +X+1$.

In degree $4$, you want those polynomials $X^4 + aX^3 + bX^2 + cX +1$ that have no roots (so $1+a+b+c+1 \ne 0$, i.e. $a+b+c=1$) and that have no irreducible factor of degree $2$, i.e. that are not divided by $X^2+X+1$ (found above). A reducible factor of degree $4$ having no root would have to be $(X^2+X+1)^2 = X^4 + X^2 +1$. Therefore, the only irreducible polynomials of degree $4$ remain $X^4 + X^3 +1$, $X^4+ X+1$ and $X^4+ X^3 + X^2 + X + 1$.

Finally, the reducible polynomials $x^5 + aX^4 + bX^3 +cX^2 + dX +1$ of degree $5$ are those that have roots (i.e. $a+b+c+d=0$) and those that can be divided by $X^2+1$. Performing long division by $X^2+1$, you get the remainder $(b+d+1)x + (a+c+1)$, so in order to get the reducible polynomials impose $a+b+c+d = 0, \; b+d+1 = 0, \; a+c+1 = 0$. Solve this system (it will have several solutions); the polynomials that are not among these solutions are the irreducible ones of degree $5$.

Now that you've listed all the irreducible polynomials of degree $\le 5$, check (by performing long division or by computing the greatest common divisor) which ones divide $Q$. None will, so $Q$ is irreducible.

Below is the proof of the irreducibility criterion mentioned at the beginning of my post.

Notice that $X^{p^m} - a$ has at least one root $x$ in some algebraic closure $K$ of $\mathrm F_{p^m}$; if $y \in K$ is another root, it follows that $x^{p^m} = y^{p^m}$ and, since $r \mapsto r^{p^m}$ is an automorphism of $K$ (because the Frobenius map $r \mapsto r^p$ is), it follows that $x=y$. It follows that $X^{p^m} - a$ has exactly one root $x \in K$, of multiplicity $p^m$.

If $g \in \mathrm F_{p^m} [X]$ is the minimal polynomial of $x$, then $X^{p^m} - a = g^s$; since $p^m = s \deg g$, it follows that $s = p^t$. Let $b = -g(0)$ and assume $t>0$. Evaluating $X^{p^m} - a = g^s$ in $0$, and assuming $t>0$, we get $a = (b^{p^{t-1}})^p$ (because $-1 = (-1)^s$ in characteristic $p>0$), which would imply that $X^p - a$ has the root $b^{p^{t-1}} \in \mathrm F _{p^m}$, which would contradict the hypothesis of the criterion. It follows that $t=0$, so that $s=1$, therefore $X^{p^m} - a$ is the minimal polynomial of $a$, therefore irreducible by the definition of the concept of "minimal polynomial".