● 摘要
比线性系统更为普遍的多项式系统可用于描述大量的非线性问题. 有限域上的多项式系统在密码学与编码理论等信息科学与技术领域中有着重要应用, 因此尤为重要. 求解多项式系统是计算机代数学科中的一个主要研究课题, 同时它也促进了该学科的不断发展. 本博士论文主要研究有限域上多项式系统求解的理论、算法、实施与应用, 主要贡献总结如下. (1) 利用乘法矩阵的稀疏性提出了将零维理想的Gröbner基的项序转变为字典序的高效算法. 对于形状引理理想, 我们提出了一种概率性算法, 它分别通过计算由某个乘法矩阵所生成的线性递归序列的极小多项式以及求解结构化线性系统的方式来计算字典序Gröbner基. 针对不同的目的, 我们又提出了该算法的确定性变体与增量变体. 对于一般理想, 我们通过利用全部乘法矩阵定义线性递归关系的方式推广了上述准则, 然后利用BMS算法计算其生成多项式集合来获得字典序Gröbner基. 我们还分析了上述算法的计算复杂性与一般多项式系统中某个重要乘法矩阵的稀疏性. 算法的有效性与高效性由程序实现所验证. (2) 提出了将有限域上的多项式集合(包括零维与正维集合)分解为简单列的算法. 对于零维多项式集合, 我们通过推广有限域上一元多项式的无平方分解与利用计算由简单列所确定的扩域乘积中元素的p次根的特殊计算技巧而设计出有效的算法; 对于正维多项式集合, 我们将简单分解问题化归为正特征域上正维理想的根理想计算问题, 然后利用计算根理想的现有算法提出了有效的简单分解算法. 我们对两个算法均进行了程序实现并提供了初步的实验结果. (3) 研究了由简单列所表示的扩域非混合积上多项式的无平方分解与因式分解问题并利用多导子与形状引理理想对上述问题给予了算法化解答. 示例与实验结果说明这些算法切实有效. (4) 将有限域上多项式系统的求解方法应用于探求有限生物模型的平衡点及其个数问题与编码理论中苏丹列表解码算法插值问题中极小多项式的计算问题. 在前一应用中, 我们主要应用了基于Gröbner基的遍历算法与F2上专用三角分解算法; 在后一应用中, 我们将原问题化归为Gröbner基的换序问题并讨论了本论文中所提出的换序算法的潜在适用性.