Bases de Gröbner d'idéaux bihomogènes engendrés par des polynômes de bidegré (1,1) : algorithmes, complexité et applications.

Les systèmes multihomogènes constituent une classe importante de systèmes structurés qui interviennent dans de nombreuses applications pratiques (cryptologie, théorie des codes, géométrie effective,...). Dans cet exposé, nous nous focalisons sur les systèmes bilinéaires (i.e. bihomogènes de bidegré (1,1)) et nous les étudions dans le contexte du calcul efficace de bases de Gröbner. D'un point de vue algorithmique, nous proposons une extension du critère F5 permettant de détecter les réductions à 0 ainsi qu'une variante multihomogène de l'algorithme F5 qui exploite la structure de ces systèmes pour accélérer les calculs. Du point de vue de la complexité, nous donnons une description du module des syzygies dont les propriétés combinatoires permettent de calculer une forme explicite de la bi-série de Hilbert de l'idéal engendré par des formes bilinéaires génériques. On en déduit une nouvelle borne sur la complexité de résolution des systèmes bilinéaires affines. En particulier, cette borne permet d'identifier des sous-classes de systèmes bilinéaires affines pouvant être résolus en temps polynomial. On montre ensuite une application de ces résultats à un problème essentiel en cryptologie : le problème MinRank. Travail commun avec Jean-Charles Faugère et Mohab Safey El Din.