论文标题
关于在有限领域上不确定系统的理性解决方案的计算
On the computation of rational solutions of underdetermined systems over a finite field
论文作者
论文摘要
我们设计和分析了一种用于计算有限字段中系数的算法$ \ mathbb {f} _q $的不确定系统定义在$ \ mathbb {f} _q $上定义的系统。该算法基于减少零维搜索的量。搜索是在“垂直条”上执行的，即在给定方向上的合适尺寸的平行线性空间。我们的结果表明，平均而言，少于三个搜索就足以获得原始系统的解决方案，成功的概率随着搜索的数量而成倍增长。对我们算法的分析取决于一个随机系统的解决方案（在代数闭合$ \ mathbb {f} _q $上）具有系数的可能性，该系统中的系数在$ \ mathbb {f} _q $中满足了一定的几何学和代数属性。
We design and analyze an algorithm for computing solutions with coefficients in a finite field $\mathbb{F}_q$ of underdetermined systems defined over $\mathbb{F}_q$. The algorithm is based on reductions to zero-dimensional searches. The searches are performed on "vertical strips", namely parallel linear spaces of suitable dimension in a given direction. Our results show that, on average, less than three searches suffice to obtain a solution of the original system, with a probability of success which grows exponentially with the number of searches. The analysis of our algorithm relies on results on the probability that the solution set (over the algebraic closure of $\mathbb{F}_q$) of a random system with coefficients in $\mathbb{F}_q$ satisfies certain geometric and algebraic properties which is of independent interest.
