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

DOI10.1145/2465506.2465943MaRDI QIDQ2963233zbMATH OpenOpenAlexFDO

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)

Full work available at URL https://arxiv.org/abs/1301.5612, https://hal.inria.fr/hal-00780388/file/issac53p-faugere.pdf

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)

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.

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

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)