LIP6 CNRS Sorbonne Université Tremplin Carnot Interfaces
Direct Link LIP6 » News » PhD students

BASIRI Abdolali

PhD graduated - CALFOR
Departure date : 12/01/2003
Supervision : Jean-Charles FAUGÈRE

Base de Gröbner et LLL. Arithmétiques rapides des courbes C_{ab}

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.
Defence : 11/21/2003 - LIP6
Jury members :
Faugère Jean-Charles (CNRS, LIP6)
Lazard Daniel (UPMC, LIP6)
Roy Marie-Francoise (U. Rennes I)
Traverso Carlo (U. Pisa, Italie) [Rapporteur]
Galligo André (U. Nice) [Rapporteur]
Gaudry Pierrick (CNRS, Ecole Polytechnique)
Morain Francois (Ecole Polytechnique, INRIA) [Rapporteur]

2003-2016 Publications

 Mentions légales
Site map |