1
$\begingroup$

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 ?

$\endgroup$
1
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How did you get it ? @rewritten , did you use maple or something ? or just brute force ? $\endgroup$ – Complex analysis Dec 2 '13 at 16:58
  • $\begingroup$ 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. $\endgroup$ – rewritten Dec 2 '13 at 17:11
  • $\begingroup$ Added explicit solution. $\endgroup$ – rewritten Dec 2 '13 at 17:17
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Over $\mathbb F_2$ the product of all irreducible polynomials of degree $2$ is $x^2+x+1$ which is different from $x^4-x$. Maybe you want to say "the product of all irreducible polynomials of degree $k$ with $k\mid d$ is $x^{p^{d}}-x$". $\endgroup$ – user26857 May 4 '17 at 8:30

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.