Accueil🇫🇷Chercher

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.

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

Articles connexes

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.