Paper 2024/528
The solving degrees for computing Gröbner bases of affine semi-regular polynomial sequences
Abstract
Determining the complexity of computing Gröbner bases is an important problem both in theory and in practice, and for that the solving degree plays a key role. In this paper, we study the solving degrees of affine semi-regular sequences and their homogenized sequences. Some of our results are considered to give mathematically rigorous proofs of the correctness of methods for computing Gröbner bases of the ideal generated by an affine semi-regular sequence. This paper is a sequel of the authors’ previous work and gives additional results on the solving degrees and important behaviors of Gröbner basis computation.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- Gröbner basessolving degreesemi-regular sequencesKoszul complexdegree of regularitymultivariate cryptography
- Contact author(s)
-
m-kudo @ fit ac jp
kazuhiro @ rikkyo ac jp - History
- 2024-04-06: approved
- 2024-04-04: received
- See all versions
- Short URL
- https://ia.cr/2024/528
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/528,
author = {Momonari Kudo and Kazuhiro Yokoyama},
title = {The solving degrees for computing Gröbner bases of affine semi-regular polynomial sequences},
howpublished = {Cryptology ePrint Archive, Paper 2024/528},
year = {2024},
note = {\url{https://eprint.iacr.org/2024/528}},
url = {https://eprint.iacr.org/2024/528}
}
