LIP6 CNRS Sorbonne Université Tremplin Carnot Interfaces
Direct Link LIP6 » Tin tức » Nghiên cứu sinh

BASIRI Abdolali

Tiến sĩ - CALFOR
Ngày đi : 01-12-2003
Ban lãnh đạo nghiên cứu : 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.
Bảo vệ luận án : 21-11-2003 - LIP6
Hội đồng giám khảo :
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]

Bài báo khoa học 2003-2016

 Mentions légales
Sơ đồ site |