Decidability of irreducibility in $Z[X]$

Question

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?

Answer 1

The fundamental theorem of algebra states that every $\mathbb{C}[x]$ polynomial can be broken down into linear $\mathbb{C}[x]$ factors, i.e., $a_nx^n + \cdots + a_0 = a_n(x-b_0)(x - b_1) \cdots (x - b_n)$ for some $b_0,\ldots,b_n$. There are lots of easy-to-compute ways ways to get a bound on these $b_i$ using only the original $a_j$, for example, Cauchy's bound: $$|b_i| \leq 1 + \max_{i} \left| {a_i \over a_n}\right|.$$ Since any $\mathbb{Z}[x]$ divisor of $a_nx^n + \cdots + a_0$ must be a $\mathbb{C}[x]$ divisor, it must in particular be a product of some set of $x - b_i$ and one of $a_n$'s integer factors. This lets us compute an upper bound on the coefficients of such a divisor.

---

This is a somewhat complicated proof, in that it uses more than one named theorem, and especially through the F.T. of algebra, makes some use of calculus. Perhaps there is still a cleaner argument?

Answer 2

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.