基于标签的矩阵型Grbner基算法研究
doi: 10.11999/JEIT140831
Research on Signature-based Grbner Basis Algorithms in Matrix Style
-
摘要: 目前基于标签的Grbner基算法大多是Buchberger型的,涉及矩阵型算法的文献往往是为了进行复杂度分析,而不考虑实际的效率。该文从实际应用出发,给出矩阵型Gao-Volny-Wang(GVW)算法的一个实例,提出算法层次的优化设计方法。同时,该文还给出一个高效的约化准则。通过实验,该文比较了算法可用的各项准则及策略。实验结果表明,该文的矩阵型GVW实例在准则和策略的选取上是最优的。并且,矩阵型GVW在某些多项式系统(例如,Cyclic系列和Katsura系列多项式系统)下比Buchberger型GVW要快2~6倍。
-
关键词:
- 密码学 /
- Grbner基 /
- 标签 /
- 多项式 /
- Gao-Volny-Wang (GVW)算法
Abstract: The current signature-based Grbner basis algorithms are mostly in Buchberger style and the researches related to matrix style often aim to analyze the complexity of algorithms. From a practical aspect, this paper provides a concrete Gao-Volny-Wang (GVW) algorithm in matrix style and presents optimization at the algorithmic level. Meanwhile, an efficient reduction criterion is given in the paper. Many popular criteria and strategies are compared by some experiments which show that the matrix version described in the paper is a combination of reasonable criteria and strategies. Moreover, the matrix-GVW is two to six times faster than the Buchberger style for some polynomial systems, e.g. Cyclic series and Katsura series.-
Key words:
- Cryptography /
- Grbner basis /
- Signature /
- Polynomial /
- Gao-Volny-Wang (GVW) algorithm
计量
- 文章访问数: 2057
- HTML全文浏览量: 134
- PDF下载量: 703
- 被引次数: 0