On the complexity of computing Gröbner bases for quasi-homogeneous systems

DOI10.1145/2465506.2465943zbMATH Open1360.68930arXiv1301.5612OpenAlexW2461870278MaRDI QIDQ2963233FDOQ2963233

Authors: Jean-Charles Faugère, Thibaut Verron, Mohab Safey El Din 

Publication date: 10 February 2017

Published in: Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Abstract: Let $K$ be a field and $(f_1,ldots,f_n)subsetK[X_1,ldots,X_n]$ be a sequence of quasi-homogeneous polynomials of respective weighted degrees $(d_1,ldots,d_n)$ w.r.t a system of weights $(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 $pro{d}_{i=1}^n{d}_i/pro{d}_{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.

Full work available at URL: https://arxiv.org/abs/1301.5612

Recommendations

• On the complexity of computing Gröbner bases for weighted homogeneous systems
• Sharper complexity bounds for zero-dimensional Gröbner bases and polynomial system solving
• Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree \((1,1)\): algorithms and complexity
• Sparse Gröbner bases: the unmixed case
• Solving multivariate polynomial systems and an invariant from commutative algebra

zbMATH Keywords

polynomial system solvingquasi-homogeneous polynomialsGröbner bases

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10)

Cited In (9)

• A survey on signature-based algorithms for computing Gröbner bases
• Computation of invariants of finite abelian groups
• On the complexity of the \(F_5\) Gröbner basis algorithm
• Using symmetries in the index calculus for elliptic curves discrete logarithm
• Pairing inversion for finding discrete logarithms
• On the complexity of computing Gröbner bases for weighted homogeneous systems
• On the robust hardness of Gröbner basis computation
• On the computation of Gröbner bases for matrix-weighted homogeneous systems
• Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree \((1,1)\): algorithms and complexity

This page was built for publication: On the complexity of computing Gröbner bases for quasi-homogeneous systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2963233)