2
$\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$

2 Answers 2

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

$\endgroup$
3
  • $\begingroup$ How did you get it ? @rewritten , did you use maple or something ? or just brute force ? $\endgroup$ Dec 2, 2013 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, 2013 at 17:11
  • $\begingroup$ Added explicit solution. $\endgroup$
    – rewritten
    Dec 2, 2013 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.

$\endgroup$
1
  • $\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, 2017 at 8:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .