Construction polynomiale d’algorithmes de multiplication de type Chudnovsky de complexité bilinéaire linéaire

Thèse en préparation à Aix-Marseille , dans le cadre de Mathématiques et informatique de Marseille (184), en partenariat avec l’Institut de Mathématiques de Marseille (groupe AGLR, équipe de recherche Arithmétique et Théorie de l’Information) depuis le 01-10-2018.

Membres du jury :

—Rapporteurs,

Reynald LERCIER, IRMAR, Université de Rennes (FR)

Ferruh ÖZBUDAK, Middle East Technical University (TUR)

—Examinateurs,-trices

Jean-Marc COUVEIGNES, Institut de mathématiques de Bordeaux (FR)

Nadia EL MRABET, Ecole des Mines de Sainte-Etienne (FR)

Sihem MESNAGER, Université Paris VIII (FR)

Hugues RANDRIAMBOLOLONA, ANSSI (FR)

Serge VLADUTS, Aix-Marseille Université (FR)

—Directeurs de thèse

Stéphane BALLET, Aix-Marseille Université (FR)

Alexis BONNECAZE, Aix-Marseille Université (FR)

La soutenance sera également accessible (en français) en visioconférence sur Zoom au lien suivant :
https://univ-amu-fr.zoom.us/j/85216924311?pwd=dC85OUNJbjcvWDRDbE54Y3JsMm9QQT09

ID de réunion : 852 1692 4311
Code secret : voir mail

Résumé : Cette thèse s’inscrit dans le cadre de l’arithmétique efficace dans les corps finis. 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, c’est-à-dire en genre 0. En utilisant des places de degrés croissants, nous proposons des algorithmes constructibles génériquement et en temps polynomial, qui possèdent une complexité bilinéaire asymptotique uniforme 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 d’algorithmes de type Chudnovsky hybrides, imbriquant les deux stratégies précédemment mentionnées.

Nous 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, améliorant ainsi un résultat de Bshouty (2012).

Mots clés : TBA.

Polynomial construction of Chudnovsky-type multiplication algorithms of linear bilinear complexity

Abstract: This thesis is in the context of efficient arithmetic in finite fields.

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 evaluation/interpolation algorithms on algebraic curves. There are two strategies to build such algorithms when the degree of extension grows.  The first one is to use curves of increasing genus in order to obtain enough rational places. This strategy provides algorithms with a linear bilinear complexity in the degree of the extension, but whose construction complexity is not known at this time.

The other strategy consists in fixing the genus and evaluating at places of increasing degrees. In the case of genus 1, we then obtain algorithms that can be constructed in polynomial time, whose asymptotic bilinear complexity is quasi-linear.

We start by studying the effective construction of Chudnovsky-type algorithms over the projective line, i.e. in genus 0. Using increasing degree places, we propose algorithms that are constructible in polynomial time and generically, which possess an uniform quasi-linear asymptotic bilinear complexity. We also introduce a strategy for optimizing the total complexity of these algorithms. Finally, we propose a method for the construction of hybrid Chudnovsky-type algorithms, interweaving the two previously mentioned strategies. We thus obtain for the first time Chudnovsky-type algorithms with linear bilinear complexity, which are constructible in polynomial time, thus improving a result of Bshouty (2012).

Keywords: TBA.

Liens :
https://college-doctoral.univ-amu.fr/inscrit/10943
https://adum.parisnanterre.fr/as/ed/cv.pl?mat=100379&site=adumR
https://hal.archives-ouvertes.fr/search/index/q/*/authFullName_s/Bastien+Pacifico
https://www.researchgate.net/profile/Bastien-Pacifico

Lieu : Amphithéâtre Aubert (Campus de Luminy, Polytech Marseille, bâtiment A, RDC)