Berlekamp–Zassenhaus algorithm: Difference between revisions

Revision as of 22:05, 9 January 2010

Revision as of 04:39, 10 January 2010

Line 1:

In [[mathematics]], in particular in [[computational algebra]], the '''Berlekamp-–Zassenhaus Algorithmalgorithm''' is an [[algorithm]] for factoring [[polynomial]]s over the [[integer]]s. 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 fieldsfield]]s 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==

* 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.

==External links==

* Berlekamp-–Zassenhaus' algorithm at WolframMathWorld. [http://mathworld.wolfram.com/Berlekamp-ZassenhausAlgorithm.html]

==See also==