Name
Abstract | ||
|---|---|---|
Let K be a field and (f1, ..., fn)\subset K[X1, ..., Xn] be a sequence of quasi-homogeneous polynomials of respective weighted degrees (d1, ..., dn) w.r.t a system of weights (w1,...,wn). 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 Π_{i=1n}di / Π_{i=1nwi. 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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/2465506.2465943 | ISSAC |
Keywords | DocType | Citations |
cryptography problem,homogeneous system,bner base,respective weighted degree,quasi-homogeneous structure,quasi-homogeneous case,generic zero-dimensional quasi homogeneous,generic system,quasi-homogeneous polynomial,quasi-homogeneous system,subset k,algorithms | Conference | 6 |
PageRank | References | Authors |
0.47 | 10 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jean-Charles Faugère | 1 | 1037 | 74.00 |
| Mohab Safey El Din | 2 | 450 | 35.64 |
| Thibaut Verron | 3 | 7 | 4.20 |