Solving degree, last fall degree, and related invariants

DOI10.1016/j.jsc.2022.05.001zbMath1491.13035arXiv2112.05579OpenAlexW4281554245MaRDI QIDQ2156375

Alessio Caminata, Elisa Gorla

Publication date: 18 July 2022

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

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

zbMATH Keywords

Gröbner basesCastelnuovo-Mumford regularitydegree of regularitylast fall degreesolving degree

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25) Solving polynomial systems; resultants (13P15)

Related Items

On product decomposition ⋮ Worst-case subexponential attacks on PRGs of constant degree or constant locality ⋮ The complexity of solving Weil restriction systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem
• Stronger bounds on the cost of computing Gröbner bases for HFE systems
• A new efficient algorithm for computing Gröbner bases \((F_4)\)
• On the last fall degree of zero-dimensional Weil descent systems
• Probabilistic analysis on Macaulay matrices over finite fields and complexity of constructing Gröbner bases
• Solving multivariate polynomial systems and an invariant from commutative algebra
• Depth and regularity modulo a principal ideal
• Solving Degree and Degree of Regularity for Polynomial Systems over a Finite Fields
• The Degree of Regularity of HFE Systems
• Last Fall Degree, HFE, and Weil Descent Attacks on ECDLP
• Multivariate Public Key Cryptosystems
• The Complexity of MinRank