Content deleted Content added
m WP:CHECKWIKI error 37|88|6|61 fixes + general fixes using AWB (7832) |
m added a line break to make the text a bit more readable |
||
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's lemma (number 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.
| |||