On the Complexity of Computing Gr\"obner Bases for Quasi-homogeneous Systems

Let $\text{K}$ be a field and $(f_1,\dots ,f_n)\subset \text{K}[X_1,\dots ,X_n]$ be a sequence of quasi-homogeneous polynomials of respective weighted degrees $(d_1, \ldots, d_n)$w\mathrm{.}r\mathrm{.}tasystemofweights$(w_{1},\dots,w_{n})$. Such systems are likely to arise from a lot of applications, including physics or cryptography. We design strategies for computing Gr"obner bases for quasi-homogeneous systems by adapting existing algorithms for homogeneous systems to the quasi-homogeneous case. Overall, under genericity assumptions, we show that for a generic zero-dimensional quasi-homogeneous system, the complexity of the full strategy is polynomial in the weighted B'ezout bound $\prod_{i=1}^{n}d_{i} / \prod_{i=1}^{n}w_{i}$. We provide some experimental results based on generic systems as well as systems arising from a cryptography problem. They show that taking advantage of the quasi-homogeneous structure of the systems allow us to solve systems that were out of reach otherwise.