基于标签的矩阵型Grbner基算法研究

来源：电子与信息学报杂志2015年第4期北京时间：

作者：潘森杉, 胡予濮, 王保仓

摘要：目前基于标签的Grbner基算法大多是Buchberger型的，涉及矩阵型算法的文献往往是为了进行复杂度分析，而不考虑实际的效率。该文从实际应用出发，给出矩阵型Gao-Volny-Wang(GVW)算法的一个实例，提出算法层次的优化设计方法。同时，该文还给出一个高效的约化准则。通过实验，该文比较了算法可用的各项准则及策略。实验结果表明，该文的矩阵型GVW实例在准则和策略的选取上是最优的。并且，矩阵型GVW在某些多项式系统(例如，Cyclic系列和Katsura系列多项式系统)下比Buchberger型GVW要快2~6倍。

关键词：密码学, Grbner基, 标签, 多项式, Gao-Volny-Wang (GVW)算法

基金资助：国家自然科学基金(61173151, 61173152)资助课题