On the complexity of solving generic overdetermined bilinear systems

In this paper, we study the complexity of solving overdetermined generic systems of bilinear polynomials over a finite field \begin{document}$ \mathbb{F} $\end{document} . Given a generic bilinear sequence \begin{document}$ B\in \mathbb{F}[ \textbf{x}, \textbf{y}] $\end{document} , with respect to a partition of variables \begin{document}$ \textbf{x} $\end{document} , \begin{document}$ \textbf{y} $\end{document} , we show that, the solutions of the system \begin{document}$ B = \textbf{0} $\end{document} can be efficiently found on the \begin{document}$ \mathbb{F}[ \textbf{y}] $\end{document} -module generated by \begin{document}$ B $\end{document} . Following this observation, we define notions of regularity for overdetermined bilinear systems, and we conjecture that they are generic properties. Also, we propose three variations of Grobner basis algorithms, that only involve multiplication by monomials in the \begin{document}$ \textbf{y} $\end{document} -variables, namely, \begin{document}$ \textbf{y} $\end{document} -XL, based on the XL algorithm, \begin{document}$ \textbf{y} $\end{document} -MXL, based on the mutant XL algorithm, and \begin{document}$ \textbf{y} $\end{document} -HXL, based on a hybrid approach. We develop the necessary theoretical tools to estimate the complexity of the algorithms for such sequences. We present experimental evidence for testing our conjecture, verifying our results, and comparing the complexity of the various methods. Based on the experimental data, we can conclude that \begin{document}$ \textbf{y} $\end{document} -MXL outperforms F4 on bilinear systems.