Irreducible polynomials in $\mathbb{Z}[x]$

Question

Let $f(x) \in \mathbb{Z}[x]$ be a polynomial with $1$ as the constant coefficient. Using LLL one can factor this in polynomial time. This means we can test its irreducibility in polynomial time. However what is the fastest way (both random and deterministic) to test if a polynomial(both $1$ as constant coefficient and general integers as coefficients) is irreducible or not (If $f(x)$ is irreducible, the algorithm should return say irreducible else the algorithm should say reducible)?

Answer 1

Actually one (probably) cannot factor in $\Bbb Z[x]$ in polynomial time, as the case of constant polynomials shows. However for the case of factoring primitive polynomials in $\Bbb Z[x]$, or equivalently factorin in $\Bbb Q[x]$, efficient algorithms exist, and are implemented in most computer algebra packages (which in addition can handle the multivariate case as well). I couldn't cite the precise methods from memory, but there is lots of literature on this subject; I think the most important tool is reduction modulo $p$ for appropriate primes $p$. I am not sure whether these methods can tell you reducibility without easily giving a factorization as well.