一种改进的计算F”x,y”上理想的Gr(o)bner基算法

摘要：

利用Buchberger第二准则证明了当单项式序为字典序时,多项式组G经过约化和多项式排序后,如果其中相邻元素之间的S-多项式被G除得的余式都为零,那么G就是理想<G>的Gr(o)bner基.同时,当理想的单项式序为分次逆字典序时是最容易计算出其Gr(o)bner基.改进的算法利用这两个单项式序的优点,通过在计算过程中改变单项式序,使得S-多项式的计算次数大幅减少,最终正确有效地计算出F”x,y”上理想的Gr(o)bner基.最后随机选取了几组多项式,与著名的F4算法进行对比.实验结果显示,改进算法比F4算法更快,甚至快上一个数量级,而且可以求解出相关算法不能求解的案例.

关键词： 非线性方程 S-多项式 单项式序 Gr(o)bner基算法

作者: 李良昱 彭代渊 熊玲

作者单位: 西南交通大学信息科学与技术学院,四川成都610031 西南交通大学信息科学与技术学院,四川成都610031;中国电子集团公司第三十研究所,四川成都610041

会议类型: 国内会议

会议名称: 中国密码学会2012年会

会议地点: 合肥

会议语种:中文

页码: 126-129

在线出版日期: 2012-08-09（万方平台首次上网日期，不代表论文的发表时间）