Content deleted Content added
m Removed Category:Algorithms; Adding category Category:Computer algebra (using HotCat) |
TraxPlayer (talk | contribs) mNo edit summary |
||
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_(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.
| |||