  Solving a system of $m$ multivariate quadratic equations in $n$ variables
over finite fields (the MQ problem) is one of the important problems in the
theory of computer science. The XL algorithm (XL for short) is a major approach
for solving the MQ problem with linearization over a coefficient field.
Furthermore, the hybrid approach with XL (h-XL) is a variant of XL guessing
some variables beforehand. In this paper, we present a variant of h-XL, which
we call the \textit{polynomial XL (PXL)}. In PXL, the whole $n$ variables are
divided into $k$ variables to be fixed and the remaining $n-k$ variables as
``main variables'', and we generate a Macaulay matrix with respect to the $n-k$
main variables over a polynomial ring of the $k$ (sub-)variables. By
eliminating some columns of the Macaulay matrix over the polynomial ring before
guessing $k$ variables, the amount of operations required for each guessed
value can be reduced compared with h-XL. Our complexity analysis of PXL (under
some practical assumptions and heuristics) gives a new theoretical bound, and
it indicates that PXL could be more efficient than other algorithms in theory
on the random system with $n=m$, which is the case of general multivariate
signatures. For example, on systems over the finite field with ${2^8}$ elements
with $n=m=80$, the numbers of operations deduced from the theoretical bounds of
the hybrid approaches with XL and Wiedemann XL, Crossbred, and PXL with optimal
$k$ are estimated as $2^{252}$, $2^{234}$, $2^{237}$, and $2^{220}$,
respectively.
