Algorithme de van Hoeij

En mathématiques et en algorithmique, les algorithmes de van Hoeij sont des algorithmes efficaces de factorisation des polynômes à coefficients rationnels, ou plus généralement à coefficients dans un corps de nombres ou de fonctions. Ils datent du début des années 2000, le premier article paru étant celui de Mark van Hoeij, intitulé Factoring polynomials and the knapsack problem. Des adaptations et généralisations ont ensuite été proposées par van Hoeij et d'autres auteurs.

Factoriser un polynôme à coefficients rationnels revient à factoriser un polynôme primitif à coefficients entiers. Un point commun des algorithmes de factorisation de polynômes primitifs à coefficients entiers précédemment connu est de débuter par une factorisation du polynôme modulo un nombre premier p correctement choisi, c'est-à-dire faire une factorisation dans un corps fini, ce qui est possible grâce à l'algorithme de Berlekamp ou l'algorithme de Cantor-Zassenhaus. L'idée est ensuite que cette factorisation peut être relevée, à l'aide du lemme de Hensel, en une factorisation à coefficients dans l'anneau des entiers p-adiques. Une telle factorisation est plus fine que la factorisation dans l'anneau des entiers rationnels, et cette dernière peut être retrouvée par une recherche exhaustive des produits de facteurs à coefficients p-adiques qui redonnent des polynômes à coefficients entiers. Cette dernière étape est de complexité exponentielle en le nombre de facteurs. La remontée dans l'anneau des entiers p-adiques n'est en pratique pas possible (infinité de données), mais ce problème est pallié par l'existence de bornes, dites bornes de Mignotte, qui assurent qu'une remontée dans un $\mathbf {Z} /p^{k}\mathbf {Z}$, pour un certain k assez grand par rapport à la taille des données (degré du polynôme et taille de ses coefficients) est suffisante.

Le travail de van Hoeij consiste à remplacer l'étape de recherche exhaustive par la résolution d'un problème de type sac à dos, résolu à l'aide de l'algorithme LLL. L'algorithme ainsi obtenu est de complexité polynomiale. Il ne s'agit pas du premier algorithme de complexité polynomiale résolvant ce problème, puisque Lenstra, Lenstra et Lovàsz en avaient déjà proposé un, précisément en se servant de leur algorithme LLL. Cependant, leur algorithme se révélait plus lent sur les problèmes pratiques que l'algorithme classique de complexité exponentielle. L'algorithme de van Hoeij a permis en revanche de factoriser des polynômes jusque-là inaccessibles.