Algorithmique efficace pour des opérations de base en calcul formel.

The subject of this thesis is the design and implementation of efficient algorithms for some basic operations in computer algebra, as well as their applications to related fields, such as computational number theory and cryptography. The first part of the text is dedicated to basic algorithms on univariate polynomials. The tool which we use systematically is a constructive version of Tellegen's transposition principle, which makes it possible to obtain new algorithms for the problems of multipoint evaluation and interpolation (in various polynomial bases and for various families of evaluation points), as well as a theorem of equivalence between the complexities of these two problems. The second part is devoted to fast computation with algebraic numbers. We begin by studying certain elementary operations, such as the composed sum and the composed product and their generalization -- the diamond product of Brawley and~Carlitz. Their calculation rests on the use of the formal Newton operator and the algebraic duality, translated algorithmically by the use of transposition principle and baby step / giant step methods. The results are then generalized to the framework of zero-dimensional algebraic polynomial systems, for the computation of minimal polynomials in quotient algebras and that of rational parametrizations. In the third part, we investigate the question of the efficient computation of a term in a linear recurrent sequence with polynomial coefficients. As an application, we obtain theoretical and practical improvements of a point-counting method used in hyperelliptic curve cryptography. Then, we propose an evaluation-interpolation type method for certain usual operations on linear differential operators with polynomial coefficients.Le sujet de cette thèse est 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 théorie algorithmique des nombres et la cryptographie. Une première partie traite de l'algorithmique de base sur les polynômes à une variable. L'outil systématiquement mis 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, ainsi que de paramétrisations rationnelles. 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 des 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