This is inspired by [this](https://mathoverflow.net/questions/97307/polynomials-all-of-whose-roots-are-rational)  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](https://mathoverflow.net/questions/97307/polynomials-all-of-whose-roots-are-rational) (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](https://mathoverflow.net/questions/97307/polynomials-all-of-whose-roots-are-rational) ) 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. 



Complexity of finding a rational root of a polynomial
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).


