Skip to Main content Skip to Navigation

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

Abstract : 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.
Complete list of metadata
Contributor : Ecole Polytechnique Connect in order to contact the contributor
Submitted on : Tuesday, July 27, 2010 - 10:04:41 AM
Last modification on : Wednesday, March 27, 2019 - 4:41:26 PM
Long-term archiving on: : Thursday, October 28, 2010 - 11:24:45 AM


  • HAL Id : pastel-00001023, version 1



Alin Bostan. Algorithmique efficace pour des opérations de base en calcul formel.. Algorithme et structure de données [cs.DS]. Ecole Polytechnique X, 2003. Français. ⟨pastel-00001023⟩



Record views


Files downloads