Algorithme de Berlekamp-Zassenhaus
En mathématiques, et plus particulièrement en calcul formel, l'algorithme de Berlekamp-Zassenhaus est un algorithme permettant de factoriser des polynômes à coefficients entiers. Il est nommé d'après Elwyn Berlekamp et Hans Zassenhaus. D'après le lemme de Gauss (pour les polynômes), cela permet également de factoriser les polynômes à coefficients rationnels.
L'algorithme commence par trouver une factorisation sur un corps fini adéquat, puis utilise le lemme de Hensel pour obtenir à partir d'une solution modulo (un nombre premier), une solution modulo une certaine puissance de , en utilisant la borne de Landau-Mignotte. Les facteurs dans forment alors un sous-ensemble des facteurs trouvés sur le corps fini. La complexité dans le pire cas est donc exponentielle par rapport au nombre de facteurs.
![{\displaystyle \mathbb {Z} [X]}](https://img.franco.wiki/i/5a538d203a057d4c604f799c28e9a7be410fdcac.svg)
Van Hoeij 2002 a amélioré l'algorithme en utilisant l'algorithme LLL, ce qui réduit de façon prononcée le temps nécessaire pour trouver les sous-ensembles des facteurs modulo .
Références
- (en) E. R. Berlekamp, « Factoring polynomials over finite fields », Bell System Technical Journal, vol. 46,‎ , p. 1853–1859 (DOI 10.1002/j.1538-7305.1967.tb03174.x, MR 0219231, lire en ligne).
- (en) E. R. Berlekamp, « Factoring polynomials over large finite fields », Mathematics of Computation, vol. 24,‎ , p. 713–735 (DOI 10.2307/2004849, JSTOR 2004849, MR 0276200).
- (en) David G. Cantor et Hans Zassenhaus, « A new algorithm for factoring polynomials over finite fields », Mathematics of Computation, vol. 36,‎ (DOI 10.2307/2007663, JSTOR 2007663, MR 606517).
- (en) K. O. Geddes, S. R. Czapor et G. Labahn, Algorithms for computer algebra, Boston, MA, Kluwer Academic Publishers, , 586 p. (ISBN 978-0-7923-9259-0, BNF 37409838, DOI 10.1007/b102438, MR 1256483).
- (en) Mark Van Hoeij, « Factoring polynomials and the knapsack problem », Journal of Number Theory, vol. 95,‎ (DOI 10.1016/S0022-314X(01)92763-5, MR 1924096).
- (en) Hans Zassenhaus, « On Hensel factorization. I », Journal of Number Theory, vol. 1,‎ , p. 291–311 (DOI 10.1016/0022-314X(69)90047-X, MR 0242793).