Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 23 Février 2010

Analyse de complexité des algorithmes de calcul de bases de Gröbner

par Magali Bardet (LITIS)

Les bases de Gröbner constituent un outil très puissant pour la résolution de systèmes d'équations polynomiales. Leur complexité a déjà été largement étudiée, particulièrement dans le cas d'un système comportant moins d'équations que de variables. Cette complexité se mesure en terme du degré maximal des polynômes intervenant dans le calcul de la base de Gröbner, appelé degré de régularité, et ne dépend pas de l'algorithme utilisée. Génériquement, ce degré est de l'ordre de O(n) où n est le nombre de variables du système, ce qui conduit à une complexité globale pour les calculs de bases de Gröbner qui est simplement exponentielle en le nombre de variables (alors que dans le pire cas, cette complexité peut être doublement exponentielle en le nombre de variables).

Notre contribution porte sur l'extension de ces résultats à des systèmes surdéterminés, c'est-à-dire comportant plus d'équations que de variables (ils possèdent alors un nombre fini de solutions). Nous définissons les systèmes semi-réguliers, qui modélisent les systèmes génériques, et donnons pour ces systèmes un développement asymptotique de leur degré de régularité, en utilisant des méthodes d'analyse complexe. Ces résultats sont particulièrement utilisés en cryptographie, ils permettent d'estimer la complexité des nouvelles attaques de type cryptanalyse algébrique, particulièrement efficaces sur des systèmes à clef publique.

Ce travail a été réalisé en collaboration avec Jean-Charles Faugère et Bruno Salvy.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr