This is inspired by this question. Let $f(x)=a_nx^n+...+a_0$ be a polynomial with rational coefficients. The sandard procedure of finding a rational root $p/q$ involves checking all $p$ that divide $a_0$ and all $q$ that divide $a_0$. This is not very complicated but involves factoring $a_0$ and $a_n$. The factoring problem is not known to be in P. If $n\le 4$, then the fact that the group $S_4$ is solvable and the well known formulas for roots of polynomials of degree $\le 4$ give easy polynomial time algorithm of finding rational roots.

Question Is the problem of finding a rational root of $f(x)$ in P for every $n$ (say, for $n=5$)?

Update 1 After I posted the question, I noticed an answer by Robert Israel to the previous question (of Joseph O'Rourke). That could give an answer to my question but I am still not sure how one can avoid factoring numbers $a_0,a_n$.

Update 2 Robert Israel's explanations (see his comment here ) convince me that his algorithm of checking whether a polynomial has a rational root (all roots rational) runs in polynomial time.

I removed Question 2 so that I can accept Michael Stoll's answer. I will post Question 2 as a separate question.

  • $\begingroup$ Some possible answers (by Robert Israel and 'Daniel m3') have appeared under the prior question ("Polynomials all of whose roots are rational") that Mark cites. $\endgroup$ – Joseph O'Rourke May 18 '12 at 18:12
  • $\begingroup$ Yes, and in fact Robert Israel answered Question 1 almost at the same time I posted it here. $\endgroup$ – Mark Sapir May 18 '12 at 22:05

Didn't Lenstra, Lenstra and Lovász in their famous LLL paper prove that factorization of polynomials over $\mathbb Q$ can be done in polynomial time? You get a rational root if and only if there is a factor of degree 1, and the polynomial has only rational roots if and only if all factors have degree 1.

Lenstra, A.K.; Lenstra, H.W.jun.; Lovász, László: Factoring polynomials with rational coefficients. (English) Math. Ann. 261, 515-534 (1982).

  • $\begingroup$ @Michael: I did not know this paper, unfortunately. Thank you! Looks like their algorithm does answer question 1 affirmatively. $\endgroup$ – Mark Sapir May 18 '12 at 18:29
  • 1
    $\begingroup$ What about the constant polynomials? $\endgroup$ – Steve Huntsman May 18 '12 at 19:08
  • 1
    $\begingroup$ @Steve: What about them? Most constant polynomials do not have roots. $\endgroup$ – Mark Sapir May 18 '12 at 20:50
  • 4
    $\begingroup$ [slaps head sheepishly] $\endgroup$ – Steve Huntsman May 18 '12 at 21:07

You do not need the full power of LLL algorithm for finding rational roots. In particular, Berlekamp-Zassenhaus algorithm exponential-time algorithm to compute the irreducible factorization can be used to get a polynomial-time algorithm for finding rational roots: The exponential part of this algorithm is the recombination of different modular factors to build true factors, but no such recombination is needed to build the linear factors.

A complete description and analysis of such an algorithm has been given by Loos in 1983:

Loos, R. Computing Rational Zeros of Integral Polynomials by P-Adic Expansion. SIAM Journal on Computing 12, no. 2 (May 1, 1983): 286–93. doi:10.1137/0212017.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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