Methods to see if a polynomial is irreducible Given a polynomial over a field, what are the methods to see it is irreducible? Only two comes to my mind now. First is Eisenstein criterion. Another is that if a polynomial is irreducible mod p then it is irreducible. Are there any others?
 A: To better understand the Eisenstein and related irreducibility tests you should learn about Newton polygons. It's the master theorem behind all these related results. A good place to start is Filaseta's notes - see the links below. Note: you may need to write to Filaseta to get access to his interesting book [1] on this topic.
[1] http://www.math.sc.edu/~filaseta/gradcourses/Math788F/latexbook/ 
[2] http://www.math.sc.edu/~filaseta/gradcourses/Math788F/NewtonPolygonsTalk.pdf 
[3] Newton Polygon Applet 
http://www.math.sc.edu/~filaseta/newton/newton.html
[4] Abhyankar, Shreeram S.
Historical ramblings in algebraic geometry and related algebra.
Amer. Math. Monthly 83 (1976), no. 6, 409-448.
http://links.jstor.org/sici?sici=0002-9890(197606/07)83:6%3C409:HRIAG... 
A: One method for polynomials over $\mathbb{Z}$ is to use complex analysis to say something about the location of the roots.  Often Rouche's theorem is useful; this is how Perron's criterion is proven, which says that a monic polynomial $x^n + a_{n-1} x^{n-1} + ... + a_0$ with integer coefficients is irreducible if $|a_{n-1}| > 1 + |a_{n-2}| + ... + |a_0|$ and $a_0 \neq 0$.  A basic observation is that knowing a polynomial is reducible places constraints on where its roots can be; for example, if a monic polynomial with prime constant coefficient $p$ is reducible, one of its irreducible factors has constant term $\pm p$ and the rest have constant term $\pm 1$.  It follows that the polynomial has at least one root inside the unit circle and at least one root outside.
An important thing to keep in mind here is that there exist irreducible polynomials over $\mathbb{Z}$ which are reducible modulo every prime.  For example, $x^4 + 16$ is such a polynomial.  So the modular technique is not enough in general.
A: Here's an elementary trick that I occasionally find useful: Let $y=x+c$ for some fixed integer $c$, and write $f(x)=g(y)$. Then $f$ is irreducible if and only if $g$ is irreducible. You may be able to able to reduce $g$ modulo a prime and/or apply Eisenstein to show that $g$ is irreducible.
A: Below is another method for irreducibility testing - excerpted from one of my old sci.math posts.
In 1918 Stackel published the following simple observation:
Theorem $ $ If $ p(x) $ is a composite polynomial with integer coefficients
then  $ p(n) $ is  composite for all $|n| > B $, for some bound $B$,
in fact $ p(n) $ has at most $ 2d $ prime values, where  $ d = {\rm deg}(p)$.
The simple proof can be found online in Mott & Rose [3], p. 8.
I highly recommend this delightful and stimulating 27 page paper
which discusses prime-producing polynomials and related topics.
Contrapositively, $ p(x) $ is prime (irreducible) if it assumes a prime value
for large enough $ |x| $. Conversely Bouniakowski conjectured (1857)
that prime $ p(x) $ assume infinitely many prime values (except in trivial
cases where the values of $p$ have an obvious common divisor, e.g. $ 2 | x(x+1)+2$ ).
As an example, Polya-Szego popularized A. Cohn's irreduciblity test, which
states that $ p(x) \in {\mathbb Z}[x]$ is prime if  $ p(b) $
yields a prime in radix $b$ representation (so necessarily $0 \le p_i < b$).
For example $f(x) = x^4 + 6 x^2 + 1 \pmod p$ factors for all primes $p$,
yet  $f(x)$ is prime since  $f(8) = 10601$ octal $= 4481$ is prime.
Note: Cohn's test fails if, in radix $b$, negative digits are allowed, e.g.
$f(x) = x^3 - 9 x^2 + x-9 = (x-9)(x^2 + 1)$ but $f(10) = 101$ is prime.
For further discussion see my prior post [1], along with Murty's online paper [2].
[1] Dubuque, sci.math 2002-11-12, On prime producing polynomials
http://groups.google.com/groups?selm=y8zvg4m9yhm.fsf%40nestle.ai.mit.edu 
[2] Murty, Ram.  Prime numbers and irreducible polynomials.
Amer. Math. Monthly, Vol. 109 (2002), no. 5, 452-458.
http://www.mast.queensu.ca/~murty/polya4.dvi 
[3] Mott, Joe L.; Rose, Kermit.
Prime producing cubic polynomials
Ideal theoretic methods in commutative algebra, 281-317.
Lecture Notes in Pure and Appl. Math., 220, Dekker, New York, 2001.
http://web.math.fsu.edu/~aluffi/archive/paper134.ps
A: Polynomials by Prasolov covers among others:


*

*Eisenstein's criterion

*Duma's criterion

*Irreducibility of polynomials attaining small values

*Hilbert's criterion

*Irreducibility of trinomials and fournomials

*A few algorithms for factorization

A: Reversing the polynomial. If you have a polynomial with degree $\geq 2$ and nonzero constant coefficient (otherwise it would be reducible so it wouldn't be interesting anyway), then you can reverse the coefficients and check irreducibility of that reciprocal polynomial. For example, instead of checking $f(x)=2x^4+2x^3+2x^2+2x+1$ you can check $x^4+2x^3+2x^2+2x+2$ (and see it is irreducible by Eisenstein). This corresponds to $x^4f(1/x)$.

Another useful criterion is one provided by Ram's Murty in paper already referenced in the other answer, similar to Cohn's irreducibility criteria, it states:

Murty's irreducibility criterion: Let $f(x)=a_mx^m+a_{m-1}x^{m-1}+\dots+a_1x+a_0$ be a polynomial of degree $m$ in $\mathbb{Z}[x]$ and set $$H=\max_{0\leq i\leq m-1} |a_i/a_m|.$$
If $f(n)$ is prime for some integer $n\geq H+2$, then $f(x)$ is irreducible in $\mathbb{Z}[x]$.

You can see that for example $f(x)=x^3-11x^2+19x-17$ is irreducible because of that, if you try $n=24$.


Osada's criterion. Let $f(x)=x^n+a_1x^{n-1}+\dots+a_{n-1}x\pm p$ be a polynomial with integer coefficients, where $p$ is a prime. If $p>1+|a_1|+\dots+|a_{n-1}|$, then $f(x)$ is irreducible over $\mathbb{Z}$.


Following one is also simple to use, although I found it barely applicable, nevertheless interesting:

Brauer's criterion. Let $a_1 \geq a_2 \geq \dots \geq a_n$ be positive integers and $n \geq 2$. Then the polynomial $p(x)=x^n-a_1x^{n-1}-a_2x^{n-2}-\dots-a_n$ is irreducible over $\mathbb{Z}$.


Advanced criteria related to Newton polygons. These criteria are little bit more advanced to use, but the paper below provides plenty of corollaries in terms of prime powers (such as Eisenstein criterion, but in this case with multiple primes). Schönemann–Eisenstein–Dumas-Type Irreducibility Conditions that Use Arbitrarily Many Prime Numbers. An example: try to prove irreducibility of this one $$4x^6+108x^5+108x^4+108x^3+108x^2+108x+27.$$ The article above provides way to do this (it is first example in last section of examples).

Generalizations of Cohn's irreducibility criterion.
Cohn's criterion is already mentioned, here are some generalizations from article "49598666989151226098104244512918" by Filaseta and Gross:

Filaseta and Gross (Theorem 2). Let $f(x)\in\mathbb{Z}[x]$ be polynomial with nonnegative coefficients and $f(10)$ is a prime. If $\deg f \leq 31$, then $f(x)$ is irreducible.


Filaseta and Gross (Theorem 3). Let $f(x)\in\mathbb{Z}[x]$ be polynomial with nonnegative coefficients and $f(10)$ is a prime. If each coefficient of $f$ is less than or equal to $49598666989151226098104244512918$, then $f(x)$ is irreducible.

Both results have been extended for other bases than $10$ for example in Explorations in Elementary and Analytic Number Theory and Further irreducibility criteria for polynomials with non-negative coefficients, see

Let $f(x)\in\mathbb{Z}[x]$ be a polynomial with nonnegative coefficients and $f(b)$ is a prime for some integer $b \geq 2$. If $\deg f \leq$ A359613$(b)$, then $f(x)$ is irreducible.


Let $f(x)\in\mathbb{Z}[x]$ be a polynomial with nonnegative coefficients and $f(b)$ is a prime for some integer $b\geq 3$. If each coefficient of $f$ is less than or equal to A253280$(b)$, then $f(x)$ is irreducible.
Note: Maximal bound for $b=2$ is not known, but it is shown to be between $7$ and $9$ (see the link above). So a bound of $7$ can be safely used.


Some related questions:

*

*How to choose correct strategy for irreducibility testing in $\mathbb{Z}[X]$?

*Polynomial is irreducible over $\mathbb{Q}$

*Prove that $f(x)$ is irreducible iff its reciprocal polynomial $f^*(x)$ is irreducible.
A: A polynomial $p$ with coefficients in a field $K$ (ie. $p \in K[x]$) is irreducible if and only if $K[x]/(p)$ is a field. Therefore, all elements of this quotient ring are supposed to be invertible in that case. Say that $p$ is of degree $n$, then the elements in $K[x]/(p)$ are all of the form $q(x) + (p)$, where $q$ is a polynomial of degree $n-1$ or less. This means that inverting $q$ is equivalent to solving a linear system of equations. Thus, $p$ is irreducible if and only if $q$ may not be chosen such that this system is not solvable.
Thus, if $M_q$ is the matrix for $q$, the criterion is that $\det(M_q) \neq 0$ for all $q$ (because the inverse is unique, and invertibility is equivalent to the existence of a unique solution).
This reduces our problem to the solution of a polynomial equation in $n$ variables.
