齐次F5算法的简单终止性证明

潘森杉; 胡予濮; 王保仓

doi:10.11999/JEIT141601

齐次F5算法的简单终止性证明

doi: 10.11999/JEIT141601

基金项目:

国家自然科学基金(61173151, 61173152)

计量
- 文章访问数: 1201
- HTML全文浏览量: 162
- PDF下载量: 280
- 被引次数: 0
出版历程
- 收稿日期: 2014-06-23
- 修回日期: 2015-04-24
- 刊出日期: 2015-08-19

Simpler Termination Proof on Homogeneous F5 Algorithm

摘要

摘要: 自从F5算法提出以来，出现了一批基于标签的Grbner基算法，它们使用了不同的选择策略且减少冗余多项式的准则也各不相同。为了满足正确终止性，这些算法的策略和准则必须满足一些一般的规律。根据这些规律，该文提出了一个框架，使大多数算法成为该框架的实例。随后，利用重写基的性质，得到了框架的简单正确终止证明。为了得到F5算法的简单证明，该文对F5算法的约化操作进行合理的化简。特别地，对于齐次F5算法，证明了其复杂的选择策略等价于按模序选择。这样，齐次F5算法就能看成框架的一个特例，从而得到了F5算法的简单证明。
- 密码学 /
- Grbner基 /
- 标签 /
- 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全文

参考文献(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.

施引文献

资源附件(0)

访问统计