Algorithme de Berlekamp-Zassenhaus

Modèle:Ébauche 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 $p$ (un nombre premier), une solution modulo une certaine puissance de $p$, en utilisant la borne de Landau-Mignotte. Les facteurs dans $\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.

Modèle:Harvsp 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 $p$.

Références

• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Ouvrage.
• Modèle:Article.
• Modèle:Article.

Articles connexes

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