On the computation of rational solutions of underdetermined systems over a finite field

DOI10.1016/j.jco.2022.101712OpenAlexW4307569217MaRDI QIDQ2685068

Nardo Giménez, Mariana Pérez, Melina Privitelli, Guillermo Matera

Publication date: 17 February 2023

Published in: Journal of Complexity (Search for Journal in Brave)

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

zbMATH Keywords

finite fieldsrational solutionsaverage-case complexityprobability of successunderdetermined systemsreduced regular sequences

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Rational points (14G05) Number-theoretic algorithms; complexity (11Y16) Finite ground fields in algebraic geometry (14G15) Varieties over finite and local fields (11G25)

Uses Software

• FGb

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deterministic root finding over finite fields using Graeffe transforms
• On the relation between the MXL family of algorithms and Gröbner basis algorithms
• Definability and fast quantifier elimination in algebraically closed fields
• Lectures on results on Bezout's theorem. Notes by D. P. Patil
• A new efficient algorithm for computing Gröbner bases \((F_4)\)
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• Computing parametric geometric resolutions
• Solvability of systems of polynomial congruences modulo a large prime
• La conjecture de Weil. I
• On the complexity of the \(F_5\) Gröbner basis algorithm
• On the computation of rational points of a hypersurface over a finite field
• Improved explicit estimates on the number of solutions of equations over a finite field
• Generic local structure of the morphisms in commutative algebra
• On the complexity exponent of polynomial system solving
• Randomized Root Finding over Finite FFT-fields using Tangent Graeffe Transforms
• Handbook of Finite Fields
• Hybrid approach for solving multivariate systems over finite fields
• Fast computation of a rational point of a variety over a finite field
• Finding Points on Curves over Finite Fields
• Introduction to Algebraic Geometry
• Computing one billion roots using the tangent Graeffe method
• Comparison Between XL and Gröbner Basis Algorithms
• Number of Points of Varieties in Finite Fields
• Counting Reducible, Powerful, and Relatively Irreducible Multivariate Polynomials over Finite Fields