Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 02 mars 2021 à 14h00 en visioconférence, Elisa Gorla nous parlera de : Complexity of Groebner bases computations and applications to cryptography (exposé online aux JNCF)

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 : Wednesday 12 October 2022 Valid HTML 4.01! Valid CSS! Contact pour cette page : Cyril.Banderier at