<p>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 <a href="http://en.wikipedia.org/wiki/Rational_root_theorem" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Rational_root_theorem</a>
As noted by D.W., this might be problematic if the constant coefficient is hard to factor (see also <a href="https://math.stackexchange.com/questions/123018/polynomial-and-integer-roots">https://math.stackexchange.com/questions/123018/polynomial-and-integer-roots</a>)</p>

<p>In any case, the Sage documentation clearly explains how they are doing the root search: <strong>"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)."</strong>
See <a href="http://www.sagemath.org/doc/reference/polynomial_rings/sage/rings/polynomial/polynomial_element.html" rel="nofollow noreferrer">http://www.sagemath.org/doc/reference/polynomial_rings/sage/rings/polynomial/polynomial_element.html</a>.</p>

<p>So your question becomes <em>How do they efficiently factor polynomials with integer coefficients ?</em>  Apparently, Sage is calling NTL to do that (see <a href="http://www.shoup.net/ntl/doc/ZZXFactoring.txt" rel="nofollow noreferrer">http://www.shoup.net/ntl/doc/ZZXFactoring.txt</a> for NTL details).</p>

<p>If you want an asymptotically efficient method, you could refer to the method of Lenstra, Lenstra and Lovasz (<a href="https://openaccess.leidenuniv.nl/handle/1887/3810" rel="nofollow noreferrer">https://openaccess.leidenuniv.nl/handle/1887/3810</a>).</p>

CC BY-SA 3.0
2013-07-18T18:51:06.853Z
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.
CC BY-SA 3.0
2013-07-18T18:57:32.333Z
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
CC BY-SA 3.0
2013-07-19T00:11:10.540Z
@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.
CC BY-SA 3.0
2013-07-19T08:46:03.340Z
For an asymptotically *and practically* efficient method, the best known algorithm is by van Hoeij (see [here](http://dx.doi.org/10.1016%2FS0022-314X%2801%2992763-5)). Actually, NTL seems to be using it.
Bruno
CC BY-SA 3.0
2013-07-18T18:43:58.887Z
2013-07-18T19:36:59.310Z
2017-04-13T12:19:19.363Z
minar
<p>What algorithm can we use to find all integer roots of a polynomial $f(x)$ with integer coefficients?</p>

<p>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?</p>

CC BY-SA 3.0
2013-07-18T14:13:07.440Z
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 [cs.se] which has a broader scope.
Kaveh
CC BY-SA 3.0
2013-07-18T14:15:23.057Z
Hold on.  Why does being undecidable make the question off-topic?  This is a legitimate research-level question.
Jeffε
CC BY-SA 3.0
2013-07-18T14:24:43.363Z
@JɛﬀE, (assuming that I understood the question correctly) it is not off-topic because it is undecidable, I think it would be off-topic because it is a very well-known and famous result: https://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem
Kaveh
CC BY-SA 3.0
2013-07-18T14:31:42.477Z
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ε
CC BY-SA 3.0
2013-07-18T15:04:27.367Z
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).
Mahdi Cheraghchi
CC BY-SA 3.0
2013-07-18T16:34:12.620Z
Kaveh: As long as I know problem is hard for multi variate polynomials.
user12290
CC BY-SA 3.0
2013-07-18T17:08:40.267Z
@MCH, You are right, I take back my comment.
Kaveh
CC BY-SA 3.0
2013-07-18T17:33:54.913Z
[This](http://math.stackexchange.com/questions/3550/using-grobner-bases-for-solving-polynomial-equations) might help. Note: I just know the words "Grobner basis" and have almost no idea of what they mean. So I am probably wrong. :)
Pratik Deoghare
CC BY-SA 3.0
2013-07-18T17:56:16.857Z
@Pratik You don't need Gröbner bases in the univariate case.
Yuval Filmus
<ds.algorithms><na.numerical-analysis>
Integer roots of a polynomial
user12290
# Integer roots of a polynomial

(Asked by: username_0 on 2013-07-18)

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?

**Tags:** ds.algorithms, na.numerical-analysis

> **Comments:**
> **username_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 [cs.se] which has a broader scope.  
> **username_2**: Hold on.  Why does being undecidable make the question off-topic?  This is a legitimate research-level question.  
> **username_1**: @JɛﬀE, (assuming that I understood the question correctly) it is not off-topic because it is undecidable, I think it would be off-topic because it is a very well-known and famous result: https://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem  
> **username_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.  
> **username_3**: username_1, 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).  
> **username_0**: username_1: As long as I know problem is hard for multi variate polynomials.  
> **username_1**: @MCH, You are right, I take back my comment.  
> **username_4**: [This](http://math.stackexchange.com/questions/3550/using-grobner-bases-for-solving-polynomial-equations) might help. Note: I just know the words "Grobner basis" and have almost no idea of what they mean. So I am probably wrong. :)  
> **username_5**: @Pratik You don't need Gröbner bases in the univariate case.  

---

## 1 answers

### Answer by username_6 on 2013-07-18. Score: 10 | Accepted answer

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 username_7, 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:**
> **username_7**: 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?  
> **username_6**: 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 ?  
> **username_7**: @username_6, 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.)  
> **username_8**: For an asymptotically *and practically* efficient method, the best known algorithm is by van Hoeij (see [here](http://dx.doi.org/10.1016%2FS0022-314X%2801%2992763-5)). Actually, NTL seems to be using it.  

---

