Berlekamp-Zassenhaus Algorithm

The Berlekamp-Zassenhaus algorithm factors polynomials over the integers, and is named for mathematicians Elwyn Berlekamp and Hans Zassenhaus. Using Gauss's lemma, it reduces integer polynomial factorization to factorization over a finite field, then applies Hensel's lemma to lift that factorization from modular arithmetic up to a sufficiently large prime power, before recombining the correct integer factors from subsets of the modular ones. The algorithm's worst-case running time is exponential in the number of factors found, a weakness substantially eased by Mark van Hoeij's 2002 improvement, which used the LLL lattice reduction algorithm to speed up the final subset-selection step.