Fast factorization of polynomial with integers coefficients

Question

I want to fast decompose polynomial over ring of integers (original polynomial has integer coefficients and all of factors have integer coefficients).

For example I want to decompose 4*x^6 + 20*x^5 + 29*x^4 - 14*x^3 - 71*x^2 - 48*x as (2*x^4 + 7*x^3 + 4*x^2 - 13*x - 16)*(2*x + 3)*x.

Which algorithm should I pick to avoid complexity of code and inefficiency of approach (speaking about total amount of arithmetic operations and memory consumption)?

I'm going to use the C programming language.

For example, maybe there are some good algorithms for polynomial factorization over ring of integers modulo prime number?

Answer 1

Since Sage is free and open source, you should be able to find the algorithm that Sage uses and then call it or at worst re-implement it in C. However, if you really must write a procedure from scratch, this is what I would do: First find the gcd of all the coefficients and divide that out, which makes your polynomial "content free". Then take the derivative and find the polynomial gcd of the original polynomial and its derivative. Take that factor out of the original polynomial by polynomial division, which breaks your problem into two parts: factoring a content-free, square free polynomial (p/gcd(p,p')), and factoring another polynomial (gcd(p,p')) which may not be square free. For the latter, start over at the beginning, until you have reduced the problem to factoring one or more content-free, square-free polynomials.

The next step would be to implement a factoring algorithm mod p. Berlekamp's algorithm is probably easiest, although Cantor-Zassenhaus is state of the art.

Finally, apply Zassenhaus algorithm to factor over the integers. If you find it is too slow, it can be improved using the "Lenstra-Lenstra-Lovasz lattice basis reduction algorithm". http://en.wikipedia.org/wiki/Factorization_of_polynomials#Factoring_univariate_polynomials_over_the_integers

As you can see, this is all rather complicated and depends on a great deal of theory from abstract algebra. You're much better off using the same library that Sage uses, or re-implementing the Sage implementation, or even just calling a running version of the Sage kernel from within your program.