Solving Degree and Degree of Regularity for Polynomial Systems over a Finite Fields

Jintai Ding University of Cincinnati and Chongqing University Dieter Schmidt University of Cincinnati

TBD mathscidoc:2207.43065

Number Theory and Cryptography, 34–49, 2013.1
In this paper, we try to clarify some of the questions related to a key concept in multivariate polynomial solving algorithm over a finite field: the degree of regularity. By the degree of regularity, here we refer to a concept first presented by Dubois and Gama, namely the lowest degree at which certain nontrivial degree drop of a polynomial system occurs. Currently, it is somehow commonly accepted that we can use this degree to estimate the complexity of solving a polynomial system, even though we do not have systematic empirical data or a theory to support such a claim. In this paper, we would like to clarify the situation with the help of experiments. We first define a concept of solving degree for a polynomial system. The key question we then need to clarify is the connection of solving degree and the degree of regularity with focus on quadratic systems. To exclude the cases that do not represent the general situation, we need to define when a system is degenerate and when it is irreducible. With extensive computer experiments, we show that the two concepts, the degree of regularity and the solving degree, are related for irreducible systems in the sense that the difference between the two degrees is indeed small, less than 3. But due to the limitation of our experiments, we speculate that this may not be the case for high degree cases.
No keywords uploaded!
[ Download ] [ 2022-07-14 14:23:15 uploaded by dingjt ] [ 27 downloads ] [ 0 comments ]
@inproceedings{jintai2013solving,
  title={Solving Degree and Degree of Regularity for Polynomial Systems over a Finite Fields},
  author={Jintai Ding, and Dieter Schmidt},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220714142315334026642},
  booktitle={Number Theory and Cryptography},
  pages={34–49},
  year={2013},
}
Jintai Ding, and Dieter Schmidt. Solving Degree and Degree of Regularity for Polynomial Systems over a Finite Fields. 2013. In Number Theory and Cryptography. pp.34–49. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220714142315334026642.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved