Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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
7  
Hold on. Why does being undecidable make the question off-topic? This is a legitimate research-level question. –  JɛffE Jul 18 '13 at 14:15
2  
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. –  JɛffE Jul 18 '13 at 14:31
11  
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
1  
@Pratik You don't need Gröbner bases in the univariate case. –  Yuval Filmus Jul 18 '13 at 17:56

1 Answer 1

up vote 9 down vote accepted

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 http://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).

share|improve this answer
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? –  D.W. Jul 18 '13 at 18:51
    
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 ? –  minar Jul 18 '13 at 18:57
    
Thank you very much. –  user12290 Jul 18 '13 at 20:30
    
@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.) –  D.W. Jul 19 '13 at 0: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. –  Bruno Jul 19 '13 at 8:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.