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.

2003-2016 Publications

• 2016
  • M. Boroujeni, A. Basiri, S. Rahmany, A. Valibouze : “Finding solutions of fuzzy polynomial equations systems by an Algebraic method”, Journal of Intelligent and Fuzzy Systems, vol. 30 (2), pp. 791-800, (IOS Press) (2016)
• 2015
  • M. Boroujeni, A. Basiri, S. Rahmany, A. Valibouze : “Solving Fuzzy Systems in Dual Form using Wu’s Method”, International Journal of Fuzzy Systems, vol. 17 (3), pp. 280-291, (Taiwan Fuzzy Systems Association) (2015)
  • M. Boroujeni, A. Basiri, S. Rahmany, A. Valibouze : “F4-invariant Algorithm for Computing SAGBI-Gröbner Bases”, Theoretical Computer Science, vol. 573, pp. 54-62, (Elsevier) (2015)
• 2005
  • A. Basiri, A. Enge, J.‑Ch. Faugère, N. Gürel : “The arithmetic of Jacobian groups of superelliptic cubics”, Mathematics of Computation, vol. 74 (249), pp. 389-410, (American Mathematical Society) (2005)
• 2004
  • A. Basiri, A. Enge, J.‑Ch. Faugère, N. Gürel : “Implementing the Arithmetic of C3,4 Curves”, ANTS-VI - 6^th International Symposium on Algorithmic Number Theory, vol. 3076, Lecture Notes in Computer Science, Burlington, VT, United States, pp. 87-101, (Springer) (2004)
• 2003
  • A. Basiri : “Base de Gröbner et LLL. Arithmétiques rapides des courbes C_ab”, thesis, phd defence 11/21/2003, supervision Faugère, Jean-Charles (2003)
  • A. Basiri, J.‑Ch. Faugère : “Changing the ordering of Gröbner bases with LLL: case of two variables”, ISSAC 2003 - International Symposium on Symbolic and Algebraic Computation, Philadelphia, PA, United States, pp. 23-29, (ACM Press) (2003)
  • A. Basiri, J.‑Ch. Faugère : “Changing the ordering of Gröbner Bases with LLL: Case of Two Variables”, (2003)