How much easier is testing polynomials of the form x^n + ax + b for irreducibility (in Z[x]) than testing polynomials in general? I am especially interested in the case where n is prime, which may be easier than the case of arbitrary n.
2
-
1$\begingroup$ An immediate special sub-case is the "Artin-Schreier" polynomials $x^p-x+a$, for $p$ prime, which are irreducible for $a\in\mathbb Z$ not divisible by $p$, because they are irreducible mod $p$. $\endgroup$– paul garrettCommented Jul 27, 2012 at 16:44
-
$\begingroup$ I only know the generalized Eisenstein criterion *Van der Waerden, 2nd.ed, p76-77), essentially that if a prime q exists whose highest power dividing b is q^k, where k is not a multiple of p, and if q^k also divides a, then irreducibility follows, (assuming n=p is prime). e.g. X^5 + 12X + 4. Moreover if X^n + pX + cp^2 is irreducible, then it has a linear factor. e.g. X^6 + 3X + 9 has no root mod 5 hence is irreducible. I hope this is right, as I am a novice. $\endgroup$– roy smithCommented Jul 27, 2012 at 17:46
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
For a special case (when $a=\pm 1$) see
Testing irreducibilty over small moduli (obviously, if your polynomial is irreducible modulo $p,$ it is irreducible), is described in detail in this paper of Richard Brent's.
answered Jul 27, 2012 at 21:42