Decidability of irreducibility in $Z[X]$ I am interested in a naive algorithm for testing irreducibility in $\mathbb Z[X]$: given a polynomial $p=a_nX^n+\ldots+a_0$ in $\mathbb Z[X]$, is there a known explicit bound $M=M(n,\max_{i=0}^n|a_i|)$ such that if $p$ factorizes as $qr$ in $\mathbb Z[X]$, then the coefficients of $q$ and $r$ are all bounded above by $M$ in absolute value?

An alternative idea that doesn't involve the complex roots of $p$:
Find $n+1$ distinct integers $x_0, x_1, \ldots, x_n$ such that $p(x_i) \neq 0$ for all i. Note that if $p$ factorizes as $p = qr$, then we have $p(x_i) = q(x_i) r(x_i)$ for all $i$. This gives us an upper bound on $\left|q(x_i)\right|$, and the values $q(x_i)$ fully determine the polynomial $q$ by polynomial interpolation in Lagrange form.
