Français
Complexity of Gröbner bases computations and applications to cryptography - lecture 1
Virtualconference
Authors : Gorla, Elisa (Author of the conference)
CIRM (Publisher )
13P10 - Gröbner bases; other bases for ideals and modules
Additional resources :
https://www.cirm-math.fr/RepOrga/2564/Slides/Gorla-day1.pdf
CIRM (Publisher )
Loading the player...
|
Abstract :
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
MSC Codes : Keywords : Gröbner bases; Castelnuovo-Mumford regularity; solving degree; lest fall degree
13P10 - Gröbner bases; other bases for ideals and modules
Additional resources :
https://www.cirm-math.fr/RepOrga/2564/Slides/Gorla-day1.pdf
|
Information on the Video
Film maker : Hennenfent, GuillaumeLanguage : English Available date : 19/03/2021 Conference Date : 02/03/2021 Subseries : Research School arXiv category : Commutative Algebra Mathematical Area(s) : Algebra Format : MP4 (.mp4) - HD Video Time : 01:33:37 Targeted Audience : Researchers Download : https://videos.cirm-math.fr/2021-03-02_Gorla_1.mp4 
|
Information on the Event
Event Title : French Computer Algebra Days / JNCF - Journées nationales de calcul formelEvent Organizers : Bardet, Magali ; Busé, Laurent ; Koseleff, Pierre-Vincent ; Vaccon, Tristan Dates : 01/03/2021 - 05/03/2021 Event Year : 2021 Event URL : https://conferences.cirm-math.fr/2564.html
Citation Data
DOI : 10.24350/CIRM.V.19720603Cite this video as: 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 |
See Also
- [Virtualconference] Computational real algebraic geometry and applications to robotics - lecture 2 / Author of the conference Moroz, Guillaume.
- [Virtualconference] Complexity of Gröbner bases computations and applications to cryptography - lecture 2 / Author of the conference Gorla, Elisa.
- [Virtualconference] Tree-indexed polynomials and power series - lecture 2 / Author of the conference Chapoton, Frédéric.
- [Virtualconference] Topics in structured linear algebra - lecture 2 / Author of the conference Boito, Paola.
- [Virtualconference] Computational real algebraic geometry and applications to robotics - lecture 1 / Author of the conference Moroz, Guillaume.
- [Virtualconference] Combinatorics and algebra of partially ordered sets - lecture 1 / Author of the conference Chapoton, Frédéric.
- [Virtualconference] Topics in structured linear algebra - lecture 1 / Author of the conference Boito, Paola.
Bibliography
- 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
