Factoring polynomials and the knapsack problem

For two decades the standard algorithm for factoring polynomials f with rational coecients has been the Berlekamp-Zassenhaus algorithm. The com-plexity of this algorithm depends exponentially on n, where n is the number of modular factors of f. This exponential time complexity is due to a combi-natorial problem; the problem of choosing the right subsets of these n factors. In this paper this combinatorial problem is reduced to a type of knapsack problem that can be solved with lattice reduction algorithms. The result is a practical algorithm that can factor polynomials that are far out of reach for previous algorithms. The presented solution to the combinatorial problem is dierent from previ-ous lattice based factorizers; these algorithms avoided the combinatorial prob-lem by solving the entire factorization problem with lattice reduction. This led to lattices of large dimension and coecients, and thus poor performance. This is why lattice based algorithms, despite their polynomial time complexity, did not replace Berlekamp-Zassenhaus as the standard method. That is now changing; new versions of computer algebra systems such as Maple, Magma, NTL and Pari have already switched to the algorithm presented here. 1