  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.
