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.
References
- "Factoring polynomials over finite fields", Bell System Technical Journal 46 (8): 1853–1859, 1967, doi:10.1002/j.1538-7305.1967.tb03174.x.
- "Factoring polynomials over large finite fields", Mathematics of Computation 24 (111): 713–735, 1970, doi:10.2307/2004849.
- Cantor, David G. (1981), "A new algorithm for factoring polynomials over finite fields", Mathematics of Computation 36 (154): 587–592, doi:10.2307/2007663.
- Geddes, K. O.; Czapor, S. R.; Labahn, G. (1992), Algorithms for computer algebra, Boston, MA: Kluwer Academic Publishers, doi:10.1007/b102438, ISBN 0-7923-9259-0, Bibcode: 1992afca.book.....G, https://archive.org/details/algorithmsforcom0000gedd.
- 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.
- "On Hensel factorization. I", Journal of Number Theory 1 (3): 291–311, 1969, doi:10.1016/0022-314X(69)90047-X, Bibcode: 1969JNT.....1..291Z.
External links
- Domazet, Haris. "Berlekamp-Zassenhaus Algorithm". http://mathworld.wolfram.com/Berlekamp-ZassenhausAlgorithm.html.
See also
 |  |
