On the Complexity of Solving Generic Over-determined Bilinear Systems
share
In this paper, we study the complexity of solving generic over-determined bilinear systems over a finite field π½. Given a generic bilinear sequence B βπ½[π±,π²], with respect to a partition of variables π±, π², we show that, the solutions of the system B= 0 can be efficiently found on the π½[π²]-module generated by B. Following this observation, we propose three variations of GrΓΆbner basis algorithms, that only involve multiplication by monomials in they-variables, namely, π²-XL, based on the XL algorithm, π²-MLX, based on the mutant XL algorithm, and π²-HXL, basedon a hybrid approach. We define notions of regularity for over-determined bilinear systems,that capture the idea of genericity, and we develop the necessary theoretical tools to estimate the complexity of the algorithms for such sequences. We also present extensive experimental results, testing our conjecture, verifying our results, and comparing the complexity of the various methods.
READ FULL TEXT