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é 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.

(The room password was sent by email to the people who registered to the JNCF)

Dernière modification : Monday 24 January 2022 Valid HTML 4.01! Valid CSS! Contact pour cette page : Cyril.Banderier at