齊次F5算法的簡(jiǎn)單終止性證明

潘森杉; 胡予濮; 王保倉(cāng)

doi:10.11999/JEIT141601

齊次F5算法的簡(jiǎn)單終止性證明

doi: 10.11999/JEIT141601

基金項(xiàng)目:

國(guó)家自然科學(xué)基金(61173151, 61173152)

計(jì)量
- 文章訪問(wèn)數(shù): 1222
- HTML全文瀏覽量: 170
- PDF下載量: 280
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2014-06-23
- 修回日期: 2015-04-24
- 刊出日期: 2015-08-19

Simpler Termination Proof on Homogeneous F5 Algorithm

摘要

摘要: 自從F5算法提出以來(lái)，出現(xiàn)了一批基于標(biāo)簽的Grbner基算法，它們使用了不同的選擇策略且減少冗余多項(xiàng)式的準(zhǔn)則也各不相同。為了滿足正確終止性，這些算法的策略和準(zhǔn)則必須滿足一些一般的規(guī)律。根據(jù)這些規(guī)律，該文提出了一個(gè)框架，使大多數(shù)算法成為該框架的實(shí)例。隨后，利用重寫基的性質(zhì)，得到了框架的簡(jiǎn)單正確終止證明。為了得到F5算法的簡(jiǎn)單證明，該文對(duì)F5算法的約化操作進(jìn)行合理的化簡(jiǎn)。特別地，對(duì)于齊次F5算法，證明了其復(fù)雜的選擇策略等價(jià)于按模序選擇。這樣，齊次F5算法就能看成框架的一個(gè)特例，從而得到了F5算法的簡(jiǎn)單證明。
- 密碼學(xué) /
- Grbner基 /
- 標(biāo)簽 /
- F5算法 /
- 終止證明
Abstract: Since the F5 algorithm is proposed, a bunch of signature-based Gr?bner basis algorithms appear. They use different selection strategies to get the basis gradually and use different criteria to discard redundant polynomials as many as possible. The strategies and criteria should satisfy some general rules for correct termination. Based on these rules, a framework which include many algorithms as instances is proposed. Using the property of rewrite basis, a simple proof of the correct termination of the framework is obtained. For the simple proof of the F5 algorithm, the reduction process is simplified. In particular, for homogeneous F5 algorithm, its complicated selection strategy is proved equivalent to selecting polynomials with respect to module order. In this way, the F5 algorithm can be seen as an instance of the framework and has a rather short proof.
- Cryptography /
- Grbner basis /
- Signature /
- F5 algorithm /
- Termination proof

HTML全文

參考文獻(xiàn)(12)

Buchberger B. Ein algorithmus zum auffinden der basiselemente des restklassenrings nach einem nulldimensionalen polynomideal[D]. [Ph.D. dissertation], Universitt Innsbruck, Austria, 1965.

Faugre J C. A new efficient algorithm for computing Grbner bases (F4)[J]. Journal of Pure and Applied Algebra, 1999, 139(1-3): 61-88.

Faugre J C. A new efficient algorithm for computing Grbner bases without reduction to zero (F5)[C]. Proceedings of the 27th International Symposium on Symbolic and Algebraic Computation, New York, USA, 2002: 75-83.

Arri A and Perry J. The F5 criterion revised[J]. Journal of Symbolic Computation, 2011, 46(9): 1017-1029.

Gao Shu-hong, Guan Yin-hua, and Volny F IV. A new incremental algorithm for computing Groebner bases[C]. Proceedings of the 35th International Symposium on Symbolic and Algebraic Computation, New York, USA, 2010: 13-19.

Volny F. New algorithms for computing Grbner bases[D]. [Ph.D. dissertation], Clemson University, USA, 2011.

Sun Yao and Wang Ding-kang. A generalized criterion for signature related Grbner basis algorithms[C]. Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation, New York, USA, 2011: 337-344.

Eder C and Perry J. Signature-based algorithms to compute Grbner bases[C]. Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation, New York, USA, 2011: 99-106.

Pan Sen-shan, Hu Yu-pu, and Wang Bao-cang. The termination of the F5 algorithm revisited[C]. Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, New York, USA, 2013: 291-298.

Eder C and Roune B H. Signature rewriting in Grbner basis computation[C]. Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, New York, USA, 2013: 331-338.

Eder C. An analysis of inhomogeneous signature-based Grbner basis computations[J]. Journal of Symbolic Computation, 2013, 59(0): 21-35.

Ding Jin-tai, Cabarcas D, Schmidt D, et al.. Mutant Grbner basis algorithm[C]. Proceedings of the 1st International Conference on Symbolic Computation and Cryptography, Beijing, China, 2008: 23-32.

相關(guān)文章

施引文獻(xiàn)

資源附件(0)

訪問(wèn)統(tǒng)計(jì)