Algorithme de Berlekamp-Zassenhaus

Cet article est une ébauche concernant l’algèbre.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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 ${\displaystyle p}$ (un nombre premier), une solution modulo une certaine puissance de ${\displaystyle p}$, en utilisant la borne de Landau-Mignotte. Les facteurs dans ${\displaystyle \mathbb {Z} [X]}$ 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.

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 ${\displaystyle p}$.

• (en) E. R. Berlekamp, « Factoring polynomials over finite fields », Bell System Technical Journal, vol. 46,‎ 1967, p. 1853–1859 (DOI 10.1002/j.1538-7305.1967.tb03174.x, MR 0219231).
• (en) E. R. Berlekamp, « Factoring polynomials over large finite fields », Mathematics of Computation, vol. 24,‎ 1970, 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,‎ 1981 (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, 1992, 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,‎ 2002 (DOI 10.1016/S0022-314X(01)92763-5, MR 1924096).
• (en) Hans Zassenhaus, « On Hensel factorization. I », Journal of Number Theory, vol. 1,‎ 1969, p. 291–311 (DOI 10.1016/0022-314X(69)90047-X, MR 0242793).

• Algorithme de Berlekamp
• Lemme de Hensel
• Algorithme LLL
• Lemme de Gauss (polynômes)

• Portail de l’algèbre
• Portail de l'informatique théorique