BEGIN:VCALENDAR VERSION:2.0 PRODID:-//wp-events-plugin.com//7.2.3.1//EN TZID:Europe/Paris X-WR-TIMEZONE:Europe/Paris BEGIN:VEVENT UID:5819@i2m.univ-amu.fr DTSTART;TZID=Europe/Paris:20221215T140000 DTEND;TZID=Europe/Paris:20221215T160000 DTSTAMP:20241209T155634Z URL:https://www.i2m.univ-amu.fr/evenements/construction-polynomiale-dalgor ithmes-de-multiplication-de-type-chudnovsky-de-complexite-bilineaire-linea ire/ SUMMARY:Bastien Pacifico (I2M\, AGLRT-ATI\, Aix-Marseille Université): Con struction polynomiale d'algorithmes de multiplication de type Chudnovsky d e complexité bilinéaire linéaire DESCRIPTION:Bastien Pacifico: Construction polynomiale d'algorithmes de mul tiplication de type Chudnovsky de complexité bilinéaire linéaire\nSous la direction de Stéphane BALLET (I2M) et la codirection d'Alexis BONNECAZ E (I2M).\nThèse en préparation à Aix-Marseille \, dans le cadre de Math ématiques et informatique de Marseille (184)\, en partenariat avec l'Inst itut de Mathématiques de Marseille (groupe AGLR\, équipe de recherche Ar ithmétique et Théorie de l'Information) depuis le 01-10-2018.\nMembres d u jury :\n---Rapporteurs\,\nReynald LERCIER\, IRMAR\, Université de Renne s (FR)\nFerruh ÖZBUDAK\, Middle East Technical University (TUR)\n---Exami nateurs\,-trices\nJean-Marc COUVEIGNES\, Institut de mathématiques de Bor deaux (FR)\nNadia EL MRABET\, Ecole des Mines de Sainte-Etienne (FR)\nSihe m MESNAGER\, Université Paris VIII (FR)\nHugues RANDRIAMBOLOLONA\, ANSSI (FR)\nSerge VLADUTS\, Aix-Marseille Université (FR)\n---Directeurs de th èse\nStéphane BALLET\, Aix-Marseille Université (FR)\nAlexis BONNECAZE\ , Aix-Marseille Université (FR)\nRésumé : Cette thèse s'inscrit dans l e cadre de l'arithmétique efficace dans les corps finis. La multiplicatio n dans une extension finie d'un corps fini nécessite un certain nombre de multiplications bilinéaires\, qui dépendent des deux éléments multipl iés.  L'étude de la complexité bilinéaire consiste à réduire ce nom bre d'opérations.\nLa méthode de D.V. et G.V. Chudnovsky (1988) permet d e 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 a lgorithmes lorsque le degré de l'extension grandit.\nLa première est d'u tiliser des courbes de genres croissants afin d'obtenir suffisamment de pl aces 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.\nL'autre stratégie consis te à fixer le genre et évaluer sur des places de degrés croissants. Dan s le cas du genre 1\, on obtient alors des algorithmes constructibles en t emps polynomial\, dont la complexité bilinéaire asymptotique est quasi-l inéaire.\nNous commençons par étudier la construction effective des alg orithmes de type Chudnovsky sur la droite projective\, c'est-à-dire en ge nre 0. En utilisant des places de degrés croissants\, nous proposons des algorithmes constructibles génériquement et en temps polynomial\, qui po ssèdent une complexité bilinéaire asymptotique uniforme quasi-linéaire . Nous introduisons également une stratégie d'optimisation de la complex ité totale de ces algorithmes. Enfin\, nous proposons une méthode de con struction d'algorithmes de type Chudnovsky hybrides\, imbriquant les deux stratégies précédemment mentionnées.\nNous obtenons ainsi pour la prem ière fois des algorithmes de type Chudnovsky ayant une complexité bilin éaire linéaire\, et qui sont constructibles en temps polynomial\, améli orant ainsi un résultat de Bshouty (2012).\nPolynomial construction of Ch udnovsky-type multiplication algorithms of linear bilinear complexity\nAbs tract: This thesis is in the context of efficient arithmetic in finite fi elds.\nMultiplication in a finite extension of a finite field requires a n umber of bilinear multiplications\, which depend on the two elements being multiplied.\nThe study of bilinear complexity consists in reducing this n umber of operations. The method of D.V. and G.V. Chudnovsky (1988) allows us to construct multiplication algorithms with good bilinear complexity. T hese are evaluation/interpolation algorithms on algebraic curves. There ar e two strategies to build such algorithms when the degree of extension gro ws.  The first one is to use curves of increasing genus in order to obtai n enough rational places. This strategy provides algorithms with a linear bilinear complexity in the degree of the extension\, but whose constructio n complexity is not known at this time.\nThe other strategy consists in fi xing the genus and evaluating at places of increasing degrees. In the case of genus 1\, we then obtain algorithms that can be constructed in polynom ial time\, whose asymptotic bilinear complexity is quasi-linear.\nWe start by studying the effective construction of Chudnovsky-type algorithms over the projective line\, i.e. in genus 0. Using increasing degree places\, w e propose algorithms that are constructible in polynomial time and generic ally\, which possess an uniform quasi-linear asymptotic bilinear complexit y. We also introduce a strategy for optimizing the total complexity of the se algorithms. Finally\, we propose a method for the construction of hybri d Chudnovsky-type algorithms\, interweaving the two previously mentioned s trategies. We thus obtain for the first time Chudnovsky-type algorithms wi th linear bilinear complexity\, which are constructible in polynomial time \, thus improving a result of Bshouty (2012).\nLiens :\nhttps://college-do ctoral.univ-amu.fr/inscrit/10943\nhttps://adum.parisnanterre.fr/as/ed/cv.p l?mat=100379&\;site=adumR\nhttps://hal.archives-ouvertes.fr/search/inde x/q/*/authFullName_s/Bastien+Pacifico\nhttps://www.researchgate.net/profil e/Bastien-Pacifico\n\nLieu : Amphithéâtre Aubert (Campus de Luminy\, Pol ytech Marseille\, bâtiment A\, RDC) ATTACH;FMTTYPE=image/jpeg:https://www.i2m.univ-amu.fr/wp-content/uploads/2 020/02/Bastien_Pacifico.jpg CATEGORIES:Soutenance de thèse,AGLR,Arithmétique et Théorie de l’Information LOCATION:Luminy - Polytech Marseille\, Polytech\, Campus de Luminy\, Marsei lle\, 13009\, France X-APPLE-STRUCTURED-LOCATION;VALUE=URI;X-ADDRESS=Polytech\, Campus de Luminy \, Marseille\, 13009\, France;X-APPLE-RADIUS=100;X-TITLE=Luminy - Polytech Marseille:geo:0,0 END:VEVENT BEGIN:VTIMEZONE TZID:Europe/Paris X-LIC-LOCATION:Europe/Paris BEGIN:STANDARD DTSTART:20221030T020000 TZOFFSETFROM:+0200 TZOFFSETTO:+0100 TZNAME:CET END:STANDARD END:VTIMEZONE END:VCALENDAR