Algorithmes pour les polynômes creux : interpolation, arithmétique, test d'identité

La manipulation de polynômes est une étape souvent incontournable, que ce soit pour la résolution de problèmes théoriques ou pour la modélisation du monde physique. Dans le cadre des polynômes denses, de nombreuses années de recherches ont permis de développer des algorithmes quasi-optimaux pour les opérations les plus classiques, comme la multiplication ou l’interpolation. Cependant, pour des raisons de compromis mémoire/temps, il est souvent plus adéquat de représenter les polynômes sous une forme creuse. Dans cette représentation, l’optimalité (ou la quasi-optimalité) est bien plus difficile à atteindre. Cette thèse s’intéresse à cette problématique et présente de nouveaux algorithmes améliorant les complexités connues pour les polynômes creux.La première opération traitée est l’interpolation d’un polynôme creux. Les solutions apportées précédemment dépendent fortement du modèle sous-jacent et de l’anneau de définition sans toutefois atteindre des complexités quasi-optimales. Nos travaux répondent favorablement à cette question d’optimalité dans le cas de polynômes à coefficients entiers.Dans un second temps, la question difficile de la divisibilité entre deux polynômes creux est abordée. Tout d’abord, nous décrivons une famille non-triviale de polynômes pour laquelle nous proposons un test de divisibilité en temps polynomial. Nous proposons également des algorithmes très efficaces, optimaux dans certain cas, permettant de vérifier un produit de polynômes modulo un polynôme creux. Ces résultats permettent d’obtenir le premier algorithme quasi-linéaire de vérification de produits de polynômescreux.Enfin, les opérations arithmétiques classiques : multiplication et division sont aussi étudiées. Cette thèse montre en particulier comment s’appuyer sur la vérification et l’interpolation pour obtenir des algorithmes de produit et division exacte efficaces. Dans le cas des polynômes à coefficients entiers, notre approche permet d’obtenir pour la première fois des algorithmes quasi-optimaux.