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?
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)
In any case, the Sage documentation clearly explains how they are doing the root search: "The next method, which is used if K is an integral domain, is to attempt to factor the polynomial. If this succeeds, then for every degree-one factor a*x+b, we add -b/a as a root (as long as this quotient is actually in the desired ring)." See http://www.sagemath.org/doc/reference/polynomial_rings/sage/rings/polynomial/polynomial_element.html.
So your question becomes How do they efficiently factor polynomials with integer coefficients ? Apparently, Sage is calling NTL to do that (see http://www.shoup.net/ntl/doc/ZZXFactoring.txt for NTL details).
If you want an asymptotically efficient method, you could refer to the method of Lenstra, Lenstra and Lovasz (https://openaccess.leidenuniv.nl/handle/1887/3810).
External links referenced by this document: