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.