Research on Signature-based Grbner Basis Algorithms in Matrix Style
-
摘要: 目前基于標(biāo)簽的Grbner基算法大多是Buchberger型的，涉及矩陣型算法的文獻往往是為了進行復(fù)雜度分析，而不考慮實際的效率。該文從實際應(yīng)用出發(fā)，給出矩陣型Gao-Volny-Wang(GVW)算法的一個實例，提出算法層次的優(yōu)化設(shè)計方法。同時，該文還給出一個高效的約化準(zhǔn)則。通過實驗，該文比較了算法可用的各項準(zhǔn)則及策略。實驗結(jié)果表明，該文的矩陣型GVW實例在準(zhǔn)則和策略的選取上是最優(yōu)的。并且，矩陣型GVW在某些多項式系統(tǒng)(例如，Cyclic系列和Katsura系列多項式系統(tǒng))下比Buchberger型GVW要快2~6倍。
-
關(guān)鍵詞:
- 密碼學(xué) /
- Grbner基 /
- 標(biāo)簽 /
- 多項式 /
- 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
-
計量
- 文章訪問數(shù): 2077
- HTML全文瀏覽量: 138
- PDF下載量: 703
- 被引次數(shù): 0
下載:
