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