Berlekamp–Zassenhaus algorithm
In mathematics , in particular in computational algebra , the Berlekamp–Zassenhaus algorithm is an algorithm for factoring polynomials over the integers , named after Elwyn Berlekamp and Hans Zassenhaus . As a consequence of Gauss's lemma , this amounts to solving the problem also over the rationals.
The algorithm starts by finding factorizations over suitable finite fields using Hensel's lemma to lift the solution from modulo a prime p to a convenient power of p . After this the right factors are found as a subset of these.
The worst case of this algorithm is exponential in the number of factors.
Van Hoeij (2002) improved this algorithm by using the LLL algorithm , substantially reducing the time needed to choose the right subsets of mod p factors.
See also
References
Berlekamp, E. R. (1967), "Factoring polynomials over finite fields", Bell System Technical Journal 46 (8): 1853–1859, doi :10.1002/j.1538-7305.1967.tb03174.x , MR 0219231 Berlekamp, E. R. (1970), "Factoring polynomials over large finite fields", Mathematics of Computation 24 (111): 713–735, doi :10.2307/2004849 JSTOR 2004849 , MR 0276200 Cantor, David G.; Zassenhaus, Hans (1981), "A new algorithm for factoring polynomials over finite fields", Mathematics of Computation 36 (154): 587–592, doi :10.2307/2007663 JSTOR 2007663 , MR 0606517 Geddes, K. O.; Czapor, S. R.; Labahn, G. (1992), Algorithms for computer algebra Bibcode :1992afca.book.....G , doi :10.1007/b102438 , ISBN 0-7923-9259-0 MR 1256483 Van Hoeij, Mark (2002), "Factoring polynomials and the knapsack problem", Journal of Number Theory 95 (2): 167–189, doi :10.1016/S0022-314X(01)92763-5 MR 1924096 Zassenhaus, Hans (1969), "On Hensel factorization. I", Journal of Number Theory 1 (3): 291–311, Bibcode :1969JNT.....1..291Z , doi :10.1016/0022-314X(69)90047-X , MR 0242793
External links
