Le but de cette thèse est d'utiliser plusieurs résultats profonds de géométrie diophantienne et de géométrie algébrique pour obtenir des applications à la factorisation des polynômes lacunaires. Dans la première partie, on décrit un algorithme qui détermine une représentation des points de torsion d'une sous-variété de Gn m définie par des polynômes lacunaires. La complexité de cet algorithme est quasilinéaire en le logarithme du degré des polynômes définissant cette sous-variété. Dans la seconde partie, on s'intéresse à des systèmes surdéterminés d'équations polynomiales. On décrit un algorithme qui permet d'écrire les zéros communs de trois polynômes à deux variables comme une réunion finie d'intersections complètes en dehors d'un ouvert de A2. La complexité de cet algorithme est encore quasi-linéaire en le logarithme du degré des polynômes en entrée mais cet algorithme dépend de la validité de la conjecture de Zilber qui est encore à ce jour un problème ouvert.

La cryptographie basée sur le logarithme discret a connu de nombreuses avancées dans les dix dernières années, notamment avec l'utilisation de tores algébriques introduite par Lenstra et Verheul. Ici on axe notre travail sur la facette constructive de ces idées et se penche sur le paramétrage de ces structures. Van Dijk et Woodruff ont récemment proposé une solution pour représenter de manière compacte une famille de points d'un tore algébrique. Afin d'améliorer la complexité asymptotique de cet algorithme, on a recours à plusieurs outils. D'une part on utilise un nouveau type de bases pour les extensions de corps finis, les bases normales elliptiques dues à Couveignes et Lercier. Par ailleurs, les tailles des objets manipulés font intervenir des polynômes cyclotomiques et leurs inverses modulaires. L'amplitude de leurs coefficients intervient directement dans l'étude de complexité. Dans le cas où leurs indices sont des diviseurs d'un produit de deux nombres premiers, on parvient à des bornes voire des expressions explicites pour ces coefficients, qui permettent de conclure quant à l'amélioration du coût de communication dans des protocoles cryptographiques comme une négociation de clefs multiples de Diffie-Hellman.