Berlekamp–Zassenhaus algorithm: Difference between revisions

Revision as of 17:32, 18 January 2011

Revision as of 09:04, 12 September 2011

Line 1:

In [[mathematics]], in particular in [[computational algebra]], the '''Berlekamp–Zassenhaus algorithm''' is an [[algorithm]] for factoring [[polynomial]]s over the [[integer]]s. As a consequence of [[Gauss%27s_lemma_'s lemma (number_theorynumber theory)|Gauss's lemma]], this amounts to solving the problem also over the rationals. The algorithm starts by finding factorizations over suitable [[finite field]]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.

Line 24:

[[Category:Computer algebra]]

{{Template:Algebra-stub}}

{{Template:AlgorithmAlgebra-stub}}

{{Algorithm-stub}}