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

Appears in 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.

Information about the video

Date of recording 02/03/2021
Date of publication 19/03/2021
Institution CIRM
Licence CC BY NC ND
Language English
Audience Researchers
Director(s) Guillaume Hennenfent
Format MP4

Citation data

DOI 10.24350/CIRM.V.19720603
Cite this video 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

Domain(s)

Commutative Algebra

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

MSC codes

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

Document(s)

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

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow

Copyright Carmin.tv 2024

Give feedback