Résumé : I will start from reviewing Groebner bases and their connection to polynomial system solving. The problem of solving a polynomial system of equations over a finite field has relevant applications to cryptography and coding theory. For many of these applications, being able to estimate the complexity of computing a Groebner basis is crucial. With these applications in mind, I will review linear-algebra based algorithms, which are currently the most efficient algorithms available to compute Groebner bases. I will define and compare several invariants, that were introduced with the goal of providing an estimate on the complexity of computing a Groebner basis, including the solving degree, the degree of regularity, and the last fall degree. Concrete examples will complement the theoretical discussion.

Dernière modification : Monday 18 March 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr