TOPICS
Search

Berlekamp-Zassenhaus Algorithm


An algorithm that can be used to factor a polynomial f over the integers. The algorithm proceeds by first factoring f modulo a suitable prime p via Berlekamp's method and then uses Hensel lifting to lift this to a factorization modulo p^2, then p^4, then p^8, ..., up to some bound p^n. 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 f in Z[x] which has many different factors modulo every p.

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 p^n factors.


See also

Finite Field, Polynomial Factorization

This entry contributed by Haris Domazet

Explore with Wolfram|Alpha

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.

Referenced on Wolfram|Alpha

Berlekamp-Zassenhaus Algorithm

Cite this as:

Domazet, Haris. "Berlekamp-Zassenhaus Algorithm." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. https://mathworld.wolfram.com/Berlekamp-ZassenhausAlgorithm.html

Subject classifications