Berlekamp-Zassenhaus Algorithm
المؤلف:
Berlekamp, E. R.
المصدر:
"Factoring Polynomials over Finite Fields." Bell System Technical J. 46,
الجزء والصفحة:
...
17-1-2019
3596
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 ![Z[x]](http://mathworld.wolfram.com/images/equations/Berlekamp-ZassenhausAlgorithm/Inline9.gif)
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.
الاكثر قراءة في مواضيع عامة في الجبر
اخر الاخبار
اخبار العتبة العباسية المقدسة
