Integer roots of a polynomial

What algorithm can we use to find all integer roots of a polynomial $f(x)$ with integer coefficients?

I observe that Sage can find the roots within a few seconds even when all coefficients of $f(x)$ are very large. How is it able to do that?

• Are you looking for an algorithm to return an integer root of a given polynomial? If yes, that is undecidable and the question is off-topic here. You can ask it on Computer Science which has a broader scope. – Kaveh Jul 18 '13 at 14:13
• Hold on. Why does being undecidable make the question off-topic? This is a legitimate research-level question. – Jeffε Jul 18 '13 at 14:15
• So, then, how does Sage do it? Being undecidable—even being well-known to be undecidable—does not make the problem theoretically uninteresting. Theoretical computer scientists solve undecidable problems all the time — see, for example, all of computer-aided verification. – Jeffε Jul 18 '13 at 14:31
• Kaveh, what you are saying is not true. What is undecidable is solvability of Diophantine equations with many variables (so that there are readily infinitely many real solutions and one is searching for an integer/rational one). But this question is about a uni-variate polynomial $f(x)$, which is of course decidable (if $f(x)$ is of degree $d$, there are up to $d$ roots and one can check which one is an integer). – MCH Jul 18 '13 at 15:04
• @Pratik You don't need Gröbner bases in the univariate case. – Yuval Filmus Jul 18 '13 at 17:56

Assuming that the coefficients of $f$ are integers or rationals and that you want integer roots, the simplest approach is to use the integer or rational root theorem. See http://en.wikipedia.org/wiki/Rational_root_theorem As noted by D.W., this might be problematic if the constant coefficient is hard to factor (see also https://math.stackexchange.com/questions/123018/polynomial-and-integer-roots)