BASIRI Abdolali

Docteur - CALFOR
Date de départ : 01/12/2003
https://lip6.fr/Abdolali.Basiri

Direction de recherche : Jean-Charles FAUGÈRE

Base de Gröbner et LLL. Arithmétiques rapides des courbes Cab

L'objectif de cette thèse est d'étudier les interactions de l'Algorithme LLL (version polynomial) et les base de Gröbner.
Dans une première partie, nous calculons des formules explicites pour réaliser la loi de groupe dans la Jacobienne d'une courbe Cab pour une utilisation cryptographique. En utilisant des techniques de bases de Gröbner nous présentons une méthode permettant de calculer explicitement la loi de groupe (jacobienne) d'une courbe Cab. Avec les formules ainsi obtenues par cette méthode la loi de groupe dans la Jacobienne d'une courbe superelliptique de genre 3 peut être calculée en 131 multiplications, 10 carrés, 1 cube et 2 divisions pour l'addition.
La deuxième contribution vise à améliorer la complexité des algorithmes de changement d'ordre d'une bases de Gröbner en théorie et en pratique en utilisant l'algorithme LLL polynomial.
Nous présentons un algorithme transformant une base de Gröbner d'un idéal pour un ordre donné en une base de Gröbner pour un autre ordre qui est basé sur une version modifiée de l'algorithme LLL. La complexité théorique, dans le pire des cas, n'est pas meilleure que la complexité de l'algorithme FGLM mais on peut exprimer cette complexité en fonction de paramètres dépendant de la taille de la sortie. Ainsi lorsque les degrés de la base de Gröbner finale sont petits l'algorithme devient plus efficace. Nous présentons une première implantation en Maple qui confirme expérimentalement les bonnes performances de cet algorithme. L'algorithme est restreint au cas de deux variables mais est valide aussi en dimension positive.

Soutenance : 21/11/2003

Membres du jury :

Traverso Carlo (U. Pisa, Italie) [Rapporteur]
Galligo André (U. Nice) [Rapporteur]
Morain Francois (Ecole Polytechnique, INRIA) [Rapporteur]
Faugère Jean-Charles (CNRS, LIP6)
Lazard Daniel (UPMC, LIP6)
Roy Marie-Francoise (U. Rennes I)
Gaudry Pierrick (CNRS, Ecole Polytechnique)

Date de départ : 01/12/2003

Publications 2003-2016

Mentions légales
Carte du site