Skip to Main content Skip to Navigation
Conference papers

On the Complexity of Computing Gröbner Bases for Quasi-homogeneous Systems

Jean-Charles Faugère 1, 2 Mohab Safey El Din 1, 2 Thibaut Verron 1, 2
1 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : Let $\K$ be a field and $(f_1, \ldots, f_n)\subset \K[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öbner 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ézout 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.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-00780388
Contributor : Thibaut Verron <>
Submitted on : Wednesday, January 23, 2013 - 7:18:12 PM
Last modification on : Friday, January 8, 2021 - 5:42:02 PM
Long-term archiving on: : Wednesday, April 24, 2013 - 4:00:53 AM

Files

main_eng.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00780388, version 1
  • ARXIV : 1301.5612

Citation

Jean-Charles Faugère, Mohab Safey El Din, Thibaut Verron. On the Complexity of Computing Gröbner Bases for Quasi-homogeneous Systems. ISSAC'13 - Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation (2013), Jun 2013, Boston, United States. ⟨hal-00780388v1⟩

Share

Metrics

Record views

70

Files downloads

139