next up previous
Next: Hermite's method Up: HermiteHorowitz, Rothstein, Previous: Square-free factorization.

Algorithm for square-free decomposition

If is the square-free factorization of a, then it is clear that

and hence that c = GCD is


Then w has the same roots as a, but all are simple. It is clear that if we define by

then we can find by a simple division:

Thus two GCD calculations get us the factor corresponding to the simple roots of , and a reduced polynomial whose form is the same as that of a but with one factor removed and all powers reduced. Applying this process recursively, we are done. (Note that some improvements can still be made). See the Maple routine sqrfree for an implementation of this algorithm in Maple.

Remark. This factorization is wholly rational. That is, if we are working with polynomials whose coefficients are rational, then the factors that we come up with will also have rational coefficients. It is this that makes Hermite's method useful.

Rob Corless
Thu Nov 16 13:46:20 PST 1995