# Finding roots of polynomials with rational coefficients

I'm looking for a general approach (or approaches) for finding the roots of polynomials with rational coefficients of higher degrees than $4$. The problem is that I need to find the exact roots and not their approximations. And also I need to find both real and complex roots.

I know that there are no methods which will work for every polynomial, but I need to find at least several methods which will work for $5$ or $6$ degree.

Could anyone please suggest a link or a book where this topic is discussed?

-
There is no general method for polynomials of degree greater than 4. You could try and solve what you need with Maple. It's a pretty good solver, but I don't know what algorithm it uses. It definitely won't give you the exact roots for degree greater than 5. If this were possible, than it would contradict the impossibility of solving the polynomial equations of higher order. – Beni Bogosel Sep 28 '11 at 10:55
@Beni: Maple and Mathematica both use the Jenkins-Traub method (a fancy version of iterating with a companion matrix) for approximately solving polynomials. OP: As deoxy says, one can certainly solve polynomials in closed form if you allow the use of things like Riemann theta functions; see Umemura for instance. They're rather ungainly though; why do you need exact solutions anyway? – J. M. Sep 28 '11 at 16:41
@J.M., finding the exact roots is a part of a more complex problem I am trying to solve. I am to implement Risch's algorithm for indefinite integration and I need to factorize a given polynomial in order to be able to do this. And thank you for your comment. I think it will help me a lot. – superM Sep 28 '11 at 16:51
FWIW: most of the computing systems just represent roots as numbered roots of certain "minimal" polynomials; e.g. Root[-1 - #1 + #1^3 & , 1, 0] for Mathematica and RootOf(x^3-x-1,x,1) for Maple. For Risch's purposes, the integration of rational functions can be "implicitly" done; witness Mathematica's RootSum[]. (Maple sums implicitly over RootOf() objects.) – J. M. Sep 28 '11 at 17:05
I have tried the Kronecker's algorithm previously and I can boast that this way I computed an integral which Mathematica was unable to compute =) – superM Sep 28 '11 at 17:30

The general quintic was solved in 1858 by Hermite using methods beyond the scope of the Abel-Ruffini theorem. Exact expressions are somewhat ungainly:

See Bring radical and this: http://mathworld.wolfram.com/QuinticEquation.html which includes a general solution of the quintic in terms of the Jacobi theta functions. I am unaware of any algorithmic implementation of the methods described on the latter page.

This question Hermite's solution of the general quintic in terms of theta functions. has links to an exposition of Hermite's method.

The following two questions over at mathoverflow discuss solutions for polynomials of degree $n\geq 5$

EDIT: I was poking around and found this preprint: Resolution of degree $≤ 6$ algebraic equations by genus two theta constants which provides a step by step algorithm.

-
Thank you very much! – superM Sep 29 '11 at 6:49

Have you read the pages below?

It'd help if you told us why you need to do that.

The only practical solutions for higher degrees are numerical methods (which can probably be better for degree 3 and 4 as well). Root isolation helps and here Descartes' rule of signs and Sturm's theorem are important.

-
The solution is known for degrees 1-4. The article gives no practical solution for higher degrees, but there were several useful links. Thank's a lot. – superM Sep 28 '11 at 10:33