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

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 ?

-

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.

-

The given polynomial in 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$.

-
How did you get it ? @rewritten , did you use maple or something ? or just brute force ? –  Complex analysis Dec 2 '13 at 16:58
Not with brute force, in $\mathbb{Z}_2$ is pretty easy to do calculations, either the coefficient is 1 or 0. So you just set arbitrary coefficients (the top degree and the constant term have of course coefficient 1). Then set equality and solve. –  rewritten Dec 2 '13 at 17:11
Added explicit solution. –  rewritten Dec 2 '13 at 17:17