Solving degree, last fall degree, and related invariants

Alessio Caminata; Elisa Gorla

Paper 2021/1611

Solving degree, last fall degree, and related invariants

Alessio Caminata

Elisa Gorla

Abstract

In this paper we study and relate several invariants connected to the solving degree of a polynomial system. This provides a rigorous framework for estimating the complexity of solving a system of polynomial equations via Groebner bases methods. Our main results include a connection between the solving degree and the last fall degree and one between the degree of regularity and the Castelnuovo-Mumford regularity.

Note: Final version.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Journal of Symbolic Computation
Keywords: degree of regularity Castelnuovo--Mumford regularity Groebner bases last fall degree solving degree
Contact author(s): caminata @ dima unige it
History: 2022-06-01: revised; 2021-12-10: received; See all versions
Short URL: https://ia.cr/2021/1611
License: CC BY

BibTeX

@misc{cryptoeprint:2021/1611,
      author = {Alessio Caminata and Elisa Gorla},
      title = {Solving degree, last fall degree, and related invariants},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/1611},
      year = {2021},
      url = {https://eprint.iacr.org/2021/1611}
}