Complexity of Gröbner bases computations and applications to cryptography - lecture 1 | Vidéo | Carmin.tv

00:00:00 / 00:00:00

Complexity of Gröbner bases computations and applications to cryptography - lecture 1

Apparaît dans la collection : 2021 - French computer algebra days / Journées nationales de calcul formel

I will start from reviewing Gröbner 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 Gröbner 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 Gröbner bases. I will define and compare several invariants, that were introduced with the goal of providing an estimate on the complexity of computing a Gröbner basis, including the solving degree, the degree of regularity, and the last fall degree. Concrete examples will complement the theoretical discussion.

Informations sur la vidéo

Date de captation 02/03/2021
Date de publication 19/03/2021
Institut CIRM
Licence CC BY NC ND
Langue Anglais
Audience Chercheurs
Réalisateur(s) Guillaume Hennenfent
Format MP4

Données de citation

DOI 10.24350/CIRM.V.19720603
Citer cette vidéo Gorla, Elisa (02/03/2021). Complexity of Gröbner bases computations and applications to cryptography - lecture 1. CIRM. Audiovisual resource. DOI: 10.24350/CIRM.V.19720603
URL https://dx.doi.org/10.24350/CIRM.V.19720603

Domaine(s)

Algèbre commutative

Bibliographie

CAMINATA, Alessio et GORLA, Elisa. Solving multivariate polynomial systems and an invariant from commutative algebra. arXiv preprint arXiv:1706.06319, 2017. - https://arxiv.org/abs/1706.06319
CAMINATA, Alessio et GORLA, Elisa. The complexity of minrank. arXiv preprint arXiv:1905.02682, 2019. - https://arxiv.org/abs/1905.02682
HUANG, Ming-Deh A., KOSTERS, Michiel, YANG, Yun, et al. On the last fall degree of zero-dimensional Weil descent systems. Journal of Symbolic Computation, 2018, vol. 87, p. 207-226. - https://arxiv.org/abs/1505.02532

Codes MSC

13P10 Gröbner bases; other bases for ideals and modules

Document(s)

https://www.cirm-math.fr/RepOrga/2564/Slides/Gorla-day1.pdf

Dernières questions liées sur MathOverflow

Pour poser une question, votre compte Carmin.tv doit être connecté à mathoverflow

Poser une question sur MathOverflow

Copyright Carmin.tv 2024

Donner son avis