  In this paper we introduce a multistep generalization of the
guess-and-determine or hybrid strategy for solving a system of multivariate
polynomial equations over a finite field. In particular, we propose performing
the exhaustive evaluation of a subset of variables stepwise, that is, by
incrementing the size of such subset each time that an evaluation leads to a
polynomial system which is possibly unfeasible to solve. The decision about
which evaluation to extend is based on a preprocessing consisting in computing
an incomplete Grobner basis after the current evaluation, which possibly
generates linear polynomials that are used to eliminate further variables. If
the number of remaining variables in the system is deemed still too high, the
evaluation is extended and the preprocessing is iterated. Otherwise, we solve
the system by a Grobner basis computation.
  Having in mind cryptanalytic applications, we present an implementation of
this strategy in an algorithm called MultiSolve which is designed for
polynomial systems having at most one solution. We prove explicit formulas for
its complexity which are based on probability distributions that can be easily
estimated by performing the proposed preprocessing on a testset of evaluations
for different subsets of variables. We prove that an optimal complexity of
MultiSolve is achieved by using a full multistep strategy with a maximum number
of steps and in turn the classical guess-and-determine strategy, which
essentially is a strategy consisting of a single step, is the worst choice.
Finally, we extensively study the behaviour of MultiSolve when performing an
algebraic attack on the well-known stream cipher Trivium.
