Complexity of finding a rational root of a polynomial - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T08:42:03Z http://mathoverflow.net/feeds/question/97329 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/97329/complexity-of-finding-a-rational-root-of-a-polynomial Complexity of finding a rational root of a polynomial Mark Sapir 2012-05-18T17:41:25Z 2012-05-19T00:27:43Z <p>This is inspired by <a href="http://mathoverflow.net/questions/97307/polynomials-all-of-whose-roots-are-rational" rel="nofollow">this </a> 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. </p> <p><b> Question</b> Is the problem of finding a rational root of \$f(x)\$ in P for every \$n\$ (say, for \$n=5\$)?</p> <p><b> Update 1</b> After I posted the question, I noticed an answer by Robert Israel to the previous <a href="http://mathoverflow.net/questions/97307/polynomials-all-of-whose-roots-are-rational" rel="nofollow"> question</a> (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\$. </p> <p><b> Update 2 </b> Robert Israel's explanations (see his comment <a href="http://mathoverflow.net/questions/97307/polynomials-all-of-whose-roots-are-rational" rel="nofollow">here </a>) convince me that his algorithm of checking whether a polynomial has a rational root (all roots rational) runs in polynomial time. </p> <p>I removed Question 2 so that I can accept Michael Stoll's answer. I will post Question 2 as a separate question. </p> http://mathoverflow.net/questions/97329/complexity-of-finding-a-rational-root-of-a-polynomial/97338#97338 Answer by Michael Stoll for Complexity of finding a rational root of a polynomial Michael Stoll 2012-05-18T18:26:02Z 2012-05-18T18:26:02Z <p>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.</p> <p>Lenstra, A.K.; Lenstra, H.W.jun.; Lovász, László: <em>Factoring polynomials with rational coefficients.</em> (English) Math. Ann. <strong>261</strong>, 515-534 (1982).</p>