齊次F5算法的簡單終止性證明
doi: 10.11999/JEIT141601 cstr: 32379.14.JEIT141601
基金項目:
國家自然科學(xué)基金(61173151, 61173152)
Simpler Termination Proof on Homogeneous F5 Algorithm
-
摘要: 自從F5算法提出以來，出現(xiàn)了一批基于標(biāo)簽的Grbner基算法，它們使用了不同的選擇策略且減少冗余多項式的準則也各不相同。為了滿足正確終止性，這些算法的策略和準則必須滿足一些一般的規(guī)律。根據(jù)這些規(guī)律，該文提出了一個框架，使大多數(shù)算法成為該框架的實例。隨后，利用重寫基的性質(zhì)，得到了框架的簡單正確終止證明。為了得到F5算法的簡單證明，該文對F5算法的約化操作進行合理的化簡。特別地，對于齊次F5算法，證明了其復(fù)雜的選擇策略等價于按模序選擇。這樣，齊次F5算法就能看成框架的一個特例，從而得到了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.
-
Key words:
- Cryptography /
- Grbner basis /
- Signature /
- F5 algorithm /
- Termination proof
-
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. -
計量
- 文章訪問數(shù): 1242
- HTML全文瀏覽量: 176
- PDF下載量: 280
- 被引次數(shù): 0
下載:
