1

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.

flag
1 
 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$. – paul garrett Jul 27 at 16:44
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. – roy smith Jul 27 at 17:46

1 Answer

1

For a special case (when $a=\pm 1$) see

http://mathoverflow.net/questions/56579/about-irreducible-trinomials

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.

link|flag

Your Answer

Get an OpenID
or

Not the answer you're looking for? Browse other questions tagged or ask your own question.