Berlekamp-Zassenhaus Algorithm

An algorithm that can be used to factor a polynomial over the integers. The algorithm proceeds by first factoring modulo a suitable prime via Berlekamp's method and then uses Hensel lifting to lift this to a factorization modulo , then , then , ..., up to some bound . This has quadratic convergence. After this procedure, the right subsets of these factors are chosen in order to obtain factors with integer coefficients. The worst-case complexity of this procedure is exponential in the number of factors, since there may be an exponential number of combinations to check. Bad examples are obtained by taking an irreducible polynomial in which has many different factors modulo every .

van Hoeij (2002) improved this algorithm by providing a better way of solving the combinatorial problem. His method uses lattice reduction (more specifically, the LLL algorithm), and it substantially reduces the time needed to choose the right subsets of mod factors.