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 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.


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de van Hoeij de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Factorisation Des Polynômes — La factorisation d un polynôme consiste à écrire celui ci comme produit de polynômes. Les factorisations intéressantes sont celles permettant d écrire le polynôme initial en produit de polynômes dont le degré serait inférieur au degré du polynôme …   Wikipédia en Français

  • Factorisation d'un polynôme — Factorisation des polynômes La factorisation d un polynôme consiste à écrire celui ci comme produit de polynômes. Les factorisations intéressantes sont celles permettant d écrire le polynôme initial en produit de polynômes dont le degré serait… …   Wikipédia en Français

  • Factorisation des polynomes — Factorisation des polynômes La factorisation d un polynôme consiste à écrire celui ci comme produit de polynômes. Les factorisations intéressantes sont celles permettant d écrire le polynôme initial en produit de polynômes dont le degré serait… …   Wikipédia en Français

  • Factorisation des polynômes — En mathématiques, la factorisation d un polynôme consiste à écrire celui ci comme produit de polynômes. Les factorisations intéressantes sont celles permettant d écrire le polynôme initial en produit de plusieurs polynômes non inversibles. Un… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”