Different ways of proving a polynomial is irreducible in finite field.

Question

Is there a general characterization of irreducible polynomials over a finite field?

I was going through a problem in finding whether $p(x):=x^7+x^5+1$ is irreducible over $\mathbb F_2[x]$ or not.

If the polynomial is of degree less than or equal to $3$ then we can easily find out if its irreducible or not by finding whether it has a root or not. In this case considering the polynomial $p(x)=f(x)\cdot g(x)$ we may be able to show the irreducibility but this doesn't seem to be a very great idea. Can anyone suggest a better idea ?

Answer 1

The given polynomial is in fact not irreducible. There is at least one decomposition:

$$ (x^2+x+1)\cdot(x^5+x^4+x^3+x+1) = x^7+x^5+1 $$

This can be found by resolving the equality for coefficients:

$$ (x^2+ax+1)\cdot(x^5+bx^4+cx^3+dx^2+ex+1) = x^7+x^5+1 $$

which, equating term by term, and ignoring the terms of degree $0$ and $7$:

$$ (a+b)x^6 + (1+ab+c)x^5 + (b+ac+d)x^4 + (c+ad+e)x^3 + (d+ae+1)x^2 + (e+a)x = x^5 $$

so

$$ a+b=0 \\ ab+c=1 \\ b+ac+d = 0\\ c+ad+e=0\\ d+ae=1\\ e+a=0 $$

which are more than enough to find the solution, given that in $\mathbb{Z}_2$, $a^2=a$ and $a+a=0$ for any $a$.

Answer 2

Over a finite field $\mathbb F_p$, the product of all irreducible polynomials of degree $d$ is $x^{p^{d}}-x$, so this polynomial is irreducible iff it divides $x^{2^{7}}-x = x^{128}-x$. Now you can just check this by computation.