Is irreducibility of polynomials $\in \mathbb{Z} [X]$ over $\mathbb{Q}$ an undecidable problem? There are a number of criteria for determining whether a polynomial $\in \mathbb{Z} [X]$ is irreducible over $\mathbb{Q}$ (the traditional ones being Eisenstein criterion and irreducibility over a prime finite field).
I was wondering if the decision problem of "Given an arbitrary polynomial $\in \mathbb{Z} [X]$, is it irreducible over $\mathbb{Q}$ or not?" is decidable or undecidable.
 A: There is a polynomial-time algorithm that decomposes any non-zero polynomial in $\mathbb{Q}[X]$ into irreducible factors. The algorithm is due to Lenstra–Lenstra–Lovász (Factoring Polynomials with Rational Coefficients).
A: There is a quick way to see that this is decidable (with terrible complexity). Let $h(x) \in \mathbb{Z}[x]$ have degree $d$. Evaluate $h$ at $d+1$ points $u_1$, $u_2$, ..., $u_{d+1}$. If any of the $h(u_i)$ are $0$, we have found a factor and we can reduce to a problem of lower degree, so suppose that $z_i:=h(u_i)$ is nonzero for $1 \leq i \leq d+1$.
There are finitely many ways to split each $z_i$ as $x_i y_i$ for integers $x_i$ and $y_i$, which we can find using a prime factorization of $z_i$.
For each splitting $(x_1, x_2, \dots, x_{d+1}, y_1, y_2, \dots, y_{d+1})$ with $x_i y_i = h(u_i)$, we can use Lagrange interpolation to find the unique polynomials of degree $\leq d$ with $f(u_i) = x_i$ and $g(v_i) = y_i$. If $\deg f + \deg g \leq d$, then we have $f(x) g(x) = h(x)$ at $d+1$ values of $x$, so we must have $f(x) g(x) = h(x)$ as a polynomial identity and we have found a factorization. Conversely, if a factorization $h(x) = f(x) g(x)$ exists, then Lagrange interpolation will find it for the splitting where $x_i = f(u_i)$, $y_i = g(u_i)$.
Of course, this is a terrible algorithm, since it involves taking the prime factorization of $d+1$ integers and then doing exponentially many cases of Lagrange interpolation. But it is the only algorithm which I know how to explain in ten minutes, so it is useful when a student asks this question. See GH from MO's answer for a good algorithm.
