Sufficiently overdetermined random polynomial systems behave like semiregular ones

Abstract

Solving systems of polynomial equations over finite fields is a fundamental problem in several areas of pure and applied mathematics. Gröbner basis methods is a family of techniques to computationally solve such systems but their complexity is poorly understood. A key parameter to estimate the complexity is the degree of regularity, that is known to be easy to compute only for a family of systems, called semiregular systems. It is not known a way to establish a priori if a system is semiregular, but it is conjectured that (under certain restrictions) a random system is semiregular with probability tending to 1. In this thesis we show that with probability tending to 1 a sufficiently overdetermined system with leading forms taken uniformly and independently at random has degree of regularity the smallest possible, as if it were semiregular. Using previously established results, this implies that sufficiently overdetermined systems of polynomial equations are solvable in polynomial time with high probability. The definition of degree of regularity was introduced in 2003 by Bardet, Faugére, and Salvy for sequences of polynomials in a multivariate polynomial ring modulo a homogeneous ideal. We extend the definition to sequences defined over a multivariate polynomial ring modulo any ideal and use this language to improve upon the known upper bounds for the complexity of computing a Gröbner basis of an ideal in the case of sufficiently overdetermined systems. We present an algorithm for computing one of the zeros of an ideal, if a Gröbner basis satisfying some properties is provided. The time complexity of this algorithm depends on the degree of regularity and it is negligible compared to the cost of constructing a Gröbner basis in the first place. Lastly, we describe a reduction to an optimisation problem of the hard mathematical problem at the base of the security assumption of the AJPS cryptosystem, one of the candidates to the first round of the NIST Post-Quantum Cryptography Standardization Process.