Bostan, Alin (2003) Fast algorithms for basic operations in computer algebra. PhD thesis STIX, EP - STIX Sciences et Technologies de l'Information et de la Communication à l'X, EP/X p.246.

Alternative Locations: http://www.imprimerie.polytechnique.fr/Theses/Files/Bostan.pdf

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.

Table of content

I Introduction
1. Introduction
II Fundamental Algorithms
2. Multiplication of polynomials, matrices and differential operators
3. Newton iteration
4. Tellegen's principle into practice
5. Polynomial evaluation and interpolation on special sets of points
6. Equivalence between polynomial evaluation and interpolation
III Fast Algorithms for Algebraic Numbers
7. Fast computation with two algebraic numbers
8. Fast algorithms for zero-dimensional polynomial systems
IV Fast Algorithms for Linear Recurrences and Differential Operators
9. Linear recurrences with polynomial coefficients
10. Fast algorithms for linear differential operators

Statistiques de consultation

Repository Staff Only: edit this item