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?

Middleclass

Why not use matlab or similar? – Perihelion

@NickRosencrantz, usually I use Sage Math for such aim. But now I'm realizing algorithm that significantly depends on polynomial factorization and also have GPU (Cuda or Opencl based) as target platform. So It should be C. – Middleclass

maybe run newtons method, find factor, polynomial division, repeat. – Gretel

You must realize that factorization over F(Z, x) cannot be faster than factorization over Z. Next step is to cast in a ghost of Viete, and factorize the coefficients. Good luck anyway. – Caldarium

@petRUShka: Can you share your C code? – Forfar

Answer 1

According to this answer on mathoverflow, Sage uses FLINT to do factorisation.

FLINT (Fast Library for Number Theory) is a C library in support of computations in number theory. It's also a research project into algorithms in number theory.

So it is possible to look and even use realisation of decomposition algorithms in that library which is well-tested and stable.

Middleclass

Answer 2

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.

Dola