Thanh-Hung Dang
I2M, Aix-Marseille Université
http://www.theses.fr/2020AIXM0131
Date(s) : 25/05/2020 iCal
14 h 00 min - 17 h 00 min
SOUTENANCE DE THÈSE
Thanh-Hung DANG (I2M, Aix-Marseille Université)
L’algorithme de type évaluation-interpolation sur des courbes algébriques, introduit par D.V et G.V Chudnovsky en 1987, est à la base des techniques algorithmiques fournissant actuellement les meilleures bornes de la complexité bilinéaire de la multiplication dans les corps finis. En particulier, ces algorithmes sont connus pour avoir asymptotiquement une complexité bilinéaire linéaire ou quasi linéaire. Mais jusqu’à présent aucun travaux ne s’était attaqué à l’analyse de leur complexité scalaire. Aussi, s’intéresse-t-on dans cette thèse à la complexité scalaire de ces algorithmes.
Plus précisément, nous présentons une stratégie générique permettant d’obtenir des algorithmes de type Chudnovsky ayant une complexité scalaire optimisée. Cette complexité est directement liée à une représentation des espaces de Riemann-Roch sous-jacents visant à l’obtention de matrices creuses.
Les résultats théoriques et numériques obtenus suggèrent que notre stratégie d’optimisation est indépendante du choix du diviseur permettant de construire les espaces de Riemann-Roch.
En utilisant cette stratégie, nous améliorons de 27\% la complexité scalaire de la construction de Baum-Shokrollahi (1992) sur le corps $\mathbb {F}_{256}/\mathbb{F}_4$. De plus, pour ce corps, notre construction est la meilleure connue en terme de complexité totale. Les sources des programmes Magma utilisés dans cette thèse sont données en appendice.
Jury :
– Laurent-Stéphane DIDIER – Rapporteur
– Sihem MESNAGER – Rapporteuse
– Daniel AUGOT – Examinateur
– Nadia EL-MRABET – Examinatrice
– Serge VLADUTS – Examinateur
– Stéphane BALLET – Co-directeur de Thèse
– Alexis BONNECAZE – Directeur de Thèse
Emplacement
Site Sud, Luminy, TPR2, Amphithéâtre Herbrand 130-134 (1er étage)
Catégories