Theoretical Computer Science
ds.algorithms na.numerical-analysis
Updated Tue, 07 Jun 2022 05:35:13 GMT

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?

Solution

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).

Comments (4)

  • +1 – Thanks for the helpful hint! Fascinating. Might you be willing to edit your answer to elaborate on how to turn this into an algorithm, and what its running time is? Is the worst-case running time exponential (because it can take subexponential time to factor, and then there might be exponentially many divisors of the leading and trailing coefficient)? If so, are there better algorithms, or is this about the best one can do? Also, doesn't this approach find only the rational roots, but not irrational roots? — Jul 18, 2013 at 18:51  
  • +0 – Rereading the question and seeing that you interpret it differently, I am no longer completely sure, but it seemed clear to me and to some commenters that the question asks about integer roots. Don't you read it that way ? — Jul 18, 2013 at 18:57  
  • +0 – @minar, you are right. Now that I re-read the question, it does seem that way. I must have read the question too quickly. (I initially misinterpreted the question as implying that we want all roots of a polynomial with integer coefficients, but on re-reading the question, that seems like a misinterpretation.) — Jul 19, 2013 at 00:11  
  • +2 – For an asymptotically and practically efficient method, the best known algorithm is by van Hoeij (see here). Actually, NTL seems to be using it. — Jul 19, 2013 at 08:46  

External Links

External links referenced by this document:

References