论文标题
关于解决通用过度确定双线性系统的复杂性
On the Complexity of Solving Generic Over-determined Bilinear Systems
论文作者
论文摘要
在本文中，我们研究了在有限字段$ \ mathbb {f} $上解决通用过度确定的双线性系统的复杂性。在\ Mathbb {f} [\ MathBf {X}，\ MathBf {y}] $的情况下，给定一个通用双线性序列$ b \ in \ Mathbb {f} [\ MathBf {X}，\ MathBf {y}] $，相对于变量的分区$ \ Mathbf {x} $，$ \ \ \ \ \ m i} $ be，我们可以在$ be上找到$ be be be be， $ \ mathbb {f} [\ mathbf {y}] $ - 由$ b $生成的模块。遵循此观察，我们提出了Gröbner基础算法的三种变化，这些变化仅涉及单一元素的繁殖，即，基于XL算法，$ \ Mathbf {y} $ - Xl $ \ mathbf {y} $ - HXL，基于混合方法。我们为过度确定的双线性系统定义了规律性的概念，这些概念捕获了通用性的概念，并开发了必要的理论工具来估计此类序列算法的复杂性。我们还提出了广泛的实验结果，测试了我们的猜想，验证我们的结果并比较各种方法的复杂性。
In this paper, we study the complexity of solving generic over-determined bilinear systems over a finite field $\mathbb{F}$. Given a generic bilinear sequence $B \in \mathbb{F}[\mathbf{x},\mathbf{y}]$, with respect to a partition of variables $\mathbf{x}$, $\mathbf{y}$, we show that, the solutions of the system $B= \mathbf{0}$ can be efficiently found on the $\mathbb{F}[\mathbf{y}]$-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, $\mathbf{y}$-XL, based on the XL algorithm, $\mathbf{y}$-MLX, based on the mutant XL algorithm, and $\mathbf{y}$-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.
