On the complexity of solving generic overdetermined bilinear systems

DOI10.3934/AMC.2021047MaRDI QIDQ6163795zbMATH OpenFDO

Authors John B. Baena, Daniel Cabarcas, Javier A. Verbel

Publication date 30 June 2023

Published in Advances in Mathematics of Communications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2006.09442

zbMATH Keywords

bilinear systemscomplexityfinite fieldsGröbner basespolynomial solving

Mathematics Subject Classification ID

Solving polynomial systems; resultants (13P15) Vector spaces, linear dependence, rank, lineability (15A03) Symbolic computation and algebraic computation (68W30) Cryptography (94A60)

Abstract: In this paper, we study the complexity of solving generic over-determined bilinear systems over a finite field $mathbbF$. Given a generic bilinear sequence $BinmathbbF[mathbfx,mathbfy]$, with respect to a partition of variables $mathbfx$, $mathbfy$, we show that, the solutions of the system $B=mathbf0$ can be efficiently found on the $mathbbF[mathbfy]$-module generated by $B$. Following this observation, we propose three variations of Gr"obner basis algorithms, that only involve multiplication by monomials in they-variables, namely, $mathbfy$-XL, based on the XL algorithm, $mathbfy$-MLX, based on the mutant XL algorithm, and $mathbfy$-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.

Review text

This paper focusses on the complexity of the problem of solving bilinear algebraic systems over a field. Although the paper is present over a finite field, the authors claim that the main results are valid over any field. The analyzed bilinear systems are systems of \(m\) bilinear polynomials in \(n\) variables, over a finite field, where \(n\leq m\). Based on the observation that the solutions can be found in the \(\mathbb{F}[\mathbf{y}]\)-module generated by the system (\(\mathbb{F}\) is the field and \(\mathbf{y}\) one of the tuples variables) a conjecture on the regularity of the system and its generic properties is stated. Additionally, experimental comparisons are presented.

Recommendations

• On the asymptotic and practical complexity of solving bivariate systems over the reals
• On the complexity of solving bivariate systems
• Approximation of almost solvable bilinear systems
• On the bit complexity of solving bilinear polynomial systems
• Upper bounds on the complexity of solving systems of linear equations
• Binary solutions for overdetermined systems of linear equations
• scientific article; zbMATH DE number 4104722
• scientific article; zbMATH DE number 2169449
• On the solution and complexity of a generalized linear complementarity problem
• On computational complexity for the multiplication of generalized Hilbert matrices with vectors and solution of certain generalized linear Hilbert systems

Cites work

• A new efficient algorithm for computing Gröbner bases (F₄)
• Asymptotically faster quantum algorithms to solve multivariate quadratic equations
• Bruno Buchberger's PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. Translation from the German
• Efficient algorithms for solving overdefined systems of multivariate polynomial equations
• Flexible partial enlargement to accelerate Gröbner basis computation over \(\mathbb{F}_2\)
• Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree \((1,1)\): algorithms and complexity
• scientific article; zbMATH DE number 3857249 (Why is no real title available?)
• scientific article; zbMATH DE number 2151220 (Why is no real title available?)
• scientific article; zbMATH DE number 1418284 (Why is no real title available?)
• Hybrid approach for solving multivariate systems over finite fields
• Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
• Improvements of algebraic attacks for solving the rank decoding and MinRank problems
• Key recovery attack for all parameters of \(\mathrm{HFE}^-\)
• Key recovery attack for ZHFE
• MXL2: Solving Polynomial Equations over GF(2) Using an Improved Mutant Strategy
• On the complexity of ``Superdetermined minrank instances
• On the complexity of solving quadratic Boolean systems
• On the solvability of systems of bilinear equations in finite fields
• Solution theory for complete bilinear systems of equations
• Solving degree and degree of regularity for polynomial systems over a finite field
• Solving polynomial systems over finite fields: improved analysis of the hybrid approach
• Solving sparse linear equations over finite fields
• Sparse Gröbner bases: the unmixed case

Cited in

(4)

• Probabilistic analysis on Macaulay matrices over finite fields and complexity of constructing Gröbner bases
• On the bit complexity of solving bilinear polynomial systems
• Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree \((1,1)\): algorithms and complexity
• Multivariate signatures with polynomial factorization

This page was built for publication: On the complexity of solving generic overdetermined bilinear systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6163795)