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

DOI10.1016/J.JCO.2022.101712arXiv2206.12516MaRDI QIDQ6403103FDOQ6403103

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

Publication date: 24 June 2022

Abstract: We design and analyze an algorithm for computing solutions with coefficients in a finite field $mathbb{F}_q$ of underdetermined systems defined over $mathbb{F}_q$. The algorithm is based on reductions to zero-dimensional searches. The searches are performed on "vertical strips", namely parallel linear spaces of suitable dimension in a given direction. Our results show that, on average, less than three searches suffice to obtain a solution of the original system, with a probability of success which grows exponentially with the number of searches. The analysis of our algorithm relies on results on the probability that the solution set (over the algebraic closure of $mathbb{F}_q$) of a random system with coefficients in $mathbb{F}_q$ satisfies certain geometric and algebraic properties which is of independent interest.

Mathematics Subject Classification ID

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

This page was built for publication: On the computation of rational solutions of underdetermined systems over a finite field

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6403103)