English
Complexity of Gröbner bases computations and applications to cryptography - lecture 1
Virtualconference
Auteurs : Gorla, Elisa (Auteur de la Conférence)
CIRM (Editeur )
13P10 - Gröbner bases; other bases for ideals and modules
Ressources complémentaires :
https://www.cirm-math.fr/RepOrga/2564/Slides/Gorla-day1.pdf
CIRM (Editeur )
Loading the player...
|
Résumé :
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.
Keywords : Gröbner bases; Castelnuovo-Mumford regularity; solving degree; lest fall degree
Codes MSC : Keywords : Gröbner bases; Castelnuovo-Mumford regularity; solving degree; lest fall degree
13P10 - Gröbner bases; other bases for ideals and modules
Ressources complémentaires :
https://www.cirm-math.fr/RepOrga/2564/Slides/Gorla-day1.pdf
|
Informations sur la Vidéo
Réalisateur : Hennenfent, GuillaumeLangue : Anglais Date de publication : 19/03/2021 Date de captation : 02/03/2021 Sous collection : Research School arXiv category : Commutative Algebra Domaine : Algebra Format : MP4 (.mp4) - HD Durée : 01:33:37 Audience : Researchers Download : https://videos.cirm-math.fr/2021-03-02_Gorla_1.mp4 
|
Informations sur la Rencontre
Nom de la rencontre : French Computer Algebra Days / JNCF - Journées nationales de calcul formelOrganisateurs de la rencontre : Bardet, Magali ; Busé, Laurent ; Koseleff, Pierre-Vincent ; Vaccon, Tristan Dates : 01/03/2021 - 05/03/2021 Année de la rencontre : 2021 URL Congrès : https://conferences.cirm-math.fr/2564.html
Données de citation
DOI : 10.24350/CIRM.V.19720603Citer cette vidéo: Gorla, Elisa (2021). Complexity of Gröbner bases computations and applications to cryptography - lecture 1. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.19720603 URI : http://dx.doi.org/10.24350/CIRM.V.19720603 |
Voir aussi
- [Virtualconference] Computational real algebraic geometry and applications to robotics - lecture 2 / Auteur de la Conférence Moroz, Guillaume.
- [Virtualconference] Complexity of Gröbner bases computations and applications to cryptography - lecture 2 / Auteur de la Conférence Gorla, Elisa.
- [Virtualconference] Tree-indexed polynomials and power series - lecture 2 / Auteur de la Conférence Chapoton, Frédéric.
- [Virtualconference] Topics in structured linear algebra - lecture 2 / Auteur de la Conférence Boito, Paola.
- [Virtualconference] Computational real algebraic geometry and applications to robotics - lecture 1 / Auteur de la Conférence Moroz, Guillaume.
- [Virtualconference] Combinatorics and algebra of partially ordered sets - lecture 1 / Auteur de la Conférence Chapoton, Frédéric.
- [Virtualconference] Topics in structured linear algebra - lecture 1 / Auteur de la Conférence Boito, Paola.
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
