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.

REFERENCES:

Berlekamp, E. R. "Factoring Polynomials over Finite Fields." Bell System Technical J. 46, 1853-1859, 1967.

Berlekamp, E. R. "Factoring Polynomials over Finite Fields." Math. Comput. 24, 713-735, 1970.

Cantor, D. G. and Zassenhaus, H. "A New Algorithm for Factoring Polynomials over Finite Fields." Math. Comput. 36, 587-592, 1981.

Geddes, K. O.; Czapor, S. R.; and Labahn, G. Algorithms for Computer Algebra. Amsterdam, Netherlands: Kluwer, 1992.

van Hoeij, M. "Factoring Polynomials and the Knapsack Problem." J. Number Th. 95, 167-189, 2002.

Zassenhaus, H. "On Hensel Factorization, I." J. Number Th. 1, 291-311, 1969.