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.



Is irreducibility of polynomials $\in \mathbb{Z} [X]$ over $\mathbb{Q}$ an undecidable problem?
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](http://www.digizeitschriften.de/dms/img/?PID=PPN235181684_0261%7Clog91)).


