Polynomial construction of Chudnovsky-type algorithms with a linear bilinear complexity ; Construction polynomiale d'algorithmes de multiplication de type Chudnovsky de complexité bilinéaire linéaire
You can manage bookmarks using lists, please log in to your user account for this.
Media type:
Text;
E-Book;
Electronic Thesis
Title:
Polynomial construction of Chudnovsky-type algorithms with a linear bilinear complexity ; Construction polynomiale d'algorithmes de multiplication de type Chudnovsky de complexité bilinéaire linéaire
Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
La multiplication dans une extension finie d'un corps fini nécessite un certain nombre de multiplications bilinéaires, qui dépendent des deux éléments multipliés. L'étude de la complexité bilinéaire consiste à réduire ce nombre d'opérations.La méthode de D.V. et G.V. Chudnovsky (1988) permet de construire des algorithmes de multiplication ayant une bonne complexité bilinéaire. Ce sont des algorithmes d'évaluation/interpolation sur les courbes algébriques. Il existe deux stratégies pour construire de tels algorithmes lorsque le degré de l'extension grandit. La première est d'utiliser des courbes de genres croissants afin d'obtenir suffisamment de places rationnelles. Celle-ci fournit des algorithmes ayant une complexité bilinéaire linéaire en le degré de l'extension, mais dont la complexité de construction n'est pas connue à ce jour. L'autre stratégie consiste à fixer le genre et évaluer sur des places de degrés croissants. Dans le cas du genre 1, on obtient alors des algorithmes constructibles en temps polynomial, dont la complexité bilinéaire asymptotique est quasi-linéaire. Nous commençons par étudier la construction effective des algorithmes de type Chudnovsky sur la droite projective. Nous proposons des algorithmes constructibles génériquement et en temps polynomial, qui possèdent une complexité bilinéaire quasi-linéaire. Nous introduisons également une stratégie d'optimisation de la complexité totale de ces algorithmes. Enfin, nous proposons une méthode de construction hybride, et obtenons ainsi pour la première fois des algorithmes de type Chudnovsky ayant une complexité bilinéaire linéaire, et qui sont constructibles en temps polynomial. ; Multiplication in a finite extension of a finite field requires a number of bilinear multiplications, which depend on the two elements being multiplied. The study of bilinear complexity consists in reducing this number of operations.The method of D.V. and G.V. Chudnovsky (1988) allows us to construct multiplication algorithms with good bilinear complexity. These are ...