Probabilistic analysis on Macaulay matrices over finite fields and complexity of constructing Gröbner bases

Igor Semaev and Andrea Tenti

Abstract

Gröbner basis methods are used to solve systems of polynomial equations over finite fields, but their complexity is poorly understood. In this work an upper bound on the time complexity of constructing a Gröbner basis and finding a solutions of a system is proved. A key parameter in this estimate is the degree of regularity of the leading forms of the polynomials. Therefore, we provide an upper bound on the degree of regularity for a sufficiently overdetermined system of forms over any finite field. The bound holds with probability tending to 1 and depends only on the number of variables, the number of polynomials, and their degrees. Our results imply that sufficiently overdetermined systems of polynomial equations are solvable in polynomial time with high probability.

Available format(s)
Category
Foundations
Publication info
Published elsewhere. Journal of Algebra
DOI
10.1016/j.jalgebra.2020.08.035
Keywords
Polynomial equation systemsfinite fieldsMacaulay matricesGroebner basesmultisetscomplexity
Contact author(s)
andrea tenti @ uib no
History
2020-10-02: last of 2 revisions
See all versions
Short URL
https://ia.cr/2019/903

CC BY

BibTeX

@misc{cryptoeprint:2019/903,
author = {Igor Semaev and Andrea Tenti},
title = {Probabilistic analysis on Macaulay matrices over finite fields and complexity of constructing Gröbner bases},
howpublished = {Cryptology ePrint Archive, Paper 2019/903},
year = {2019},
doi = {10.1016/j.jalgebra.2020.08.035},
note = {\url{https://eprint.iacr.org/2019/903}},
url = {https://eprint.iacr.org/2019/903}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.