BASIRI Abdolali

毕业博士 - CALFOR
离开日期 : 2003-12-1
https://lip6.fr/Abdolali.Basiri

责任导师 : 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.

答辩 : 2003-11-21

评委会 :

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)

离开日期 : 2003-12-1

2003-2016 刊物

Mentions légales
网站导航