Thread: Polynomial factorization algortihms

Hi,

I want to write a computer program that takes a univariate polynomial of any degree with rational coefficients, and factorizes it into smaller polynomials. I am only interested in factorizing it into a product of polynomials with rational coefficients. Can someone tell me what is the best algorithm (or algorithms) to use, and be able to explain them simply?

My approach would probably start by making sure the polynomial is in standard form, removing 'obvious' factors (eg. 10x^4 + 5x^2 + 20x = 5x(2x^3 + x + 4)), and converting the rational coefficients to integer coefficients (eg. 5/3x^2 + 7/2x = 1/6(10x^2 + 21x)). This would leave me with a polynomial with coprime integer coefficients.

From here, I could use the rational roots test and long division to find the linear factors of the polynomial.

It is from here on that I'm not quite sure what to do. There maybe cases where the polynomial can be factorized into non-linear polynomials. I know that there exists algorithms, but the details are either too sketchy to implement, or use math terminology that is way over my head, and I can't follow the explanation. I think Berlekamp and Cantor-Zassenhaus are examples. It would be good if someone could point me to a good explanation of how these algorithms work in plain English (or even pseudocode or an example piece of code that has already been written).

Cheers.

Yes, you have to consider cases where the polynomial has non-real roots and therefore, cannot factor into linear polynomials with real coefficients.

Factoring a polynomial is equivalent to finding the zeros of the polynomial, e.g. x-r is a factor if and only if r is a root. So if you've got a good method to find the roots of a polynomial (I'm not a computer geek, but Newton's method?) then you're all set.