Abstract EN:

Les bases de Gröbner constituent un outil important dans la résolution de systèmes d'équations polynomiales dans les corps finis. Les algorithmes F4 et F5 proposés par J-C. Faugère utilisent respectivement une représentation matricielle qui ramène l'arithmétique polynomiale à l'algèbre linéaire, et un nouveau critère de sélection des paires critiques, permettant de générer des matrices de rang plein (si le système initial constitue une suite régulière). Cette thèse est consacrée à l'étude de l'algèbre linéaire intervenant dans le calcul d'une base de Gröbner avec les algorithmes F4 et F5. Après avoir présenté la théorie des bases de Gröbner, nous nous sommes intéressés aux produits matriciels creux et denses, en proposant des implémentations tenant compte des contraintes matérielles. Ensuite, nous avons défini un nouvel algorithme, parallélisable en grande partie, de calcul d'une forme échelon réduite qui tient compte de la structure quasiment triangulaire par bloc générées par F4 et F5. Nous avons également donné une version spécifique au corps GF(2) utilisant d'une part l'arithmétique binaire des processeurs, et d'autre part les propriétés des codes de Gray (algorithme des 4 russes adapté au cas creux). Enfin, ces résultats ont été appliqués au calcul de l'immunité algébrique et d'un annulateur d'une fonction booléenne par le calcul d'un élément du noyau d’une matrice (qui, exprimée dans une base convenable a aussi une structure triangulaire par blocs) , et par le calcul d’une base de Gröbner (à partir du système composé de la forme normale de la fonction et des équations de corps). Un algorithme générant des matrices de plus petites dimensions a été présenté.