基于签名的Groebner基算法及其应用

Many problems, which are appeared in scientific research and practical engineering, can be transfered into polynomial equations, and the key to solve these problems is solving these equations. Computing the Groebner bases of polynomial systems is an effective method to solve polynomail euqations. This research project will study the theories and algorithms of signature-based Groebner basis. Signature-based Groebner basis algorithm with uniforms for polynomial ring over field, solvable polynomial algebra and local ring will be proposed, and efficient implementation will be given on computer algebra systems. Further more, Groebner basis will be applied to polynomial equations solving and machine proving of geometric theorems.

科学研究和实际工程中产生的许多问题都可以转化为多项式方程组求解问题，求解多项式方程组是解决这类问题的关键。计算多项式系统的Groebner基是求解多项式方程组的有效方法。该项目将研究多项式系统签名Groebner基的相关理论和算法，给出统一形式的签名Groebner基算法（包括数域上的多项式环，可解多项代数以及局部环）， 并在计算机代数系统中加以实现。进一步， Groebner基将被应用于代数方程组求解和几何定理机器证明。

科学研究和实际工程中产生的许多问题都可以转化为多项式方程组求解问题，求解多项式方程组是解决这类问题的关键。 多项式系统的Groebner基是求解多项式方程.组的重要工具。项目研究了多项式系统签名Groebner基的相关理论和算法，给出了统一形式的签名Groebner基算法, 并在计算机代数系统Maple中实现。在几何自动证明领域，我们给出了几何命题在假设条件的部分分支上成立的判定方法。多变元多项式矩阵分解在系统控制和信号处理等领域具有广泛的应用，我们针对某一类型的多项式矩阵，得到了分解算法。Keccak算法被密码学中著名SHA-3算法标准所采用，我们解决了关于Keccak算法的一个挑战问题。 MDS矩阵在对称密码体系的扩散层中广泛使用，我们构造了大量最轻量MDS矩阵。