Résumé :

Cette thèse aborde la conception et l'implantation d'algorithmes efficaces pour des opérations de base en calcul formel, ainsi que leurs applications à des domaines connexes, comme la cryptographie et la théorie effective des nombres.

Une première partie traite de l'algorithmique de base sur les polynômes à une variable. L'outil mis systématiquement en oeuvre est une version constructive du principe de transposition de Tellegen, qui permet d'obtenir de nouveaux algorithmes pour l'évaluation multipoint et l'interpolation (dans diverses bases polynomiales et pour diverses familles de points d'évaluation), ainsi qu'un théorème d'équivalence entre les complexités de ces deux problèmes.

La deuxième partie est consacrée à l'algorithmique des nombres algébriques. Nous étudions d'abord certaines opérations élémentaires, comme la somme, le produit et leur généralisation, le produit diamant de Brawley et Carlitz. Leur calcul repose sur l'utilisation de l'opérateur de Newton formel et de la dualité algébrique, traduite algorithmiquement par l'emploi du principe de transposition et des méthodes de type pas de bébés / pas de géants. Ces méthodes sont ensuite généralisées au cadre des systèmes de polynômes de dimension zéro, pour le calcul de polynômes minimaux dans des algèbres quotient et des paramétrisations rationnelles (RUR).

Dans la troisième partie, nous étudions la question du calcul d'un terme d'une suite récurrente linéaire à coefficients polynomiaux. Comme application, nous obtenons des améliorations théoriques et pratiques de méthodes de comptage de points utilisées en cryptographie. Nous proposons ensuite une méthode de type évaluation-interpolation pour certaines opérations usuelles sur les opérateurs différentiels linéaires à coefficients polynomiaux.

Membres du jury :

Richard Brent (rapporteur)
Philippe Flajolet (examinateur)
Marc Giusti (directeur)
François Morain (examinateur)
Jean-Pierre Ramis (examinateur, président du jury)
Bruno Salvy (directeur)
Gilles Villard (rapporteur)