Factoring polynomials and the knapsack problem

Mark van Hoeij

Although a polynomial time algorithm exists, the most commonly used algorithm for factoring a univariate polynomial $f$ with integer coefficients is the Berlekamp-Zassenhaus algorithm which has a complexity that depends exponentially on $n$ where $n$ is the number of modular factors of $f$. This exponential time complexity is due to a combinatorial problem; the problem of choosing the right subset of these $n$ factors. In this paper we reduce this combinatorial problem to a knapsack problem of a kind that can be solved with polynomial time algorithms such LLL or PSLQ. The result is a practical algorithm that can factor large polynomials even when $n$ is large as well.