Supervision : Jean-Charles FAUGÈRE

Algèbre linéaire dans la résolution de systèmes polynomiaux Applications en cryptologie

Les bases de Gröbner constituent un outil important dans la résolution de systèmes d'équations polynomiales dans les corps finis. L'algorithme F4 élaboré par J-C. Faugère utilise une représentation matricielle qui permet de ramener l'arithmétique polynomiale utile pour le calcul des bases de Gröbner à l'algèbre linéaire. La réduction de polynômes modulo un idéal est alors équivalente au calcul d'une forme échelon réduite suivant les lignes de la matrice correspondante. Grâce à un nouveau critère de sélection de ce que l'on appelle des paires critiques, l'algorithme F5 conçu par J-C. Faugère, génère sous certaines hypothèses, des matrices de rang plein (si le système polynomial 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 plus particulièrement aux produits matriciels dense-dense, creux-dense et creux-creux en proposant des implémentations tenant compte des contraintes matérielles, comme l'utilisation de la mémoire cache, afin de bénéficier de toute la puissance du processeur pendant le calcul. Ensuite, nous avons proposé un nouvel algorithme, parallélisable en grande partie (particulièrement adapté aux processeurs multi-cœurs), 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 proposé une version spécifique au corps GF(2) qui utilise d'une part l'arithmétique binaire des processeurs, et d'autre part, les propriétés des codes de Gray (algorithme des quatre russes adapté au cas c! reux), afin de diminuer le nombre d'opérations effectuées. Une implantation multi-core (15000 lignes de code en langage C) a été réalisée et testée sur des exemples provenant d'applications telles que la cryptographie ou la robotique. Enfin, ces résultats ont été appliqués aux calculs de l'immunité algébrique et du calcul d'un annulateur d'une fonction booléenne en utilisant deux méthodes: d'une part, le calcul d'un élément du noyau d'une matrice à coefficients dans GF(2) qui, exprimée dans une base convenable a aussi une structure triangulaire par bloc. Nous avons proposé un nouvel algorithme matriciel de calcul de l'immunité algébrique faisant intervenir des matrices de plus petites dimensions. D'autre part, il est connu que le calcul de la base de Gröbner du système, obtenu à partir de la forme normale de la fonction et des équations de corps, permet de connaître l'immunité algébrique ainsi qu'une base de l'idéal des annulateurs. Nous avons appliqué notre nouvel algorithme pour réduire les matrices générées par ces deux méthodes.

2008-2016 Publications

• 2016
  • B. Boyer, Ch. Eder, J.‑Ch. Faugère, S. Lachartre, F. Martani : “GBLA – Gröbner Basis Linear Algebra Package”, 41^st International Symposium on Symbolic and Algebraic Computation, Waterloo, ON, Canada, pp. 135-142 (2016)
• 2010
  • J.‑Ch. Faugère, S. Lachartre : “Parallel Gaussian Elimination for Gröbner bases computations in finite fields”, Proceedings of the 4^th International Workshop on Parallel and Symbolic Computation, PASCO '10, Grenoble, France, pp. 89-97, (ACM) (2010)
• 2008
  • S. Lachartre : “Algèbre linéaire dans la résolution de systèmes polynomiaux Applications en cryptologie”, thesis, defence 12/11/2008, supervision Faugère, Jean-Charles (2008)