Algorithm to find the roots of a polynomial over integer

What is the algorithm to find the roots of a polynomial over integer? I observe that one can find the roots within few seconds in Sage even when all coefficients of are very large. I have asked in http://cstheory.stackexchange.com/questions/18406/roots-of-a-polynomial but still do not get answer.

-
Hint: Rational Roots Theorem. Note that this only directly applies to polynomials with rational coefficients. It can be extended rather to polynomials with rational coefficients easily. – Gamma Function Jul 18 '13 at 17:25
@JacobMayle:‌ The rational root theorem is one trick that helps bound the search space, but is it the only thing?‌ Is that as far as efficiency goes? – ShreevatsaR Jul 18 '13 at 17:26

1 Answer

Use the rational root test: if you have a polynomial $$a_0 + a_1x + \ldots + a_nx^n$$ with integer coefficients, all integer roots are of the form $\pm c$, where $c\vert a_0$.

Finding all roots therefore just amounts to factoring $a_0$ and some (very cheap) polynomial evaluations.

There are several techniques for proving a polynomial is irreducible over $\mathbb{Z}$ (Eisenstein's criteria, Perron's criteria) and these can rule out integer roots in special cases. But unless I were looking at polynomials with truly huge coefficients, the general algorithm I would implement would simply try all of the plausible roots.

-