## 留言板

 引用本文: 潘森杉, 胡予濮, 王保仓. 齐次F5算法的简单终止性证明[J]. 电子与信息学报, 2015, 37(8): 1989-1993.
Pan Sen-shan, Hu Yu-pu, Wang Bao-cang. Simpler Termination Proof on Homogeneous F5 Algorithm[J]. Journal of Electronics and Information Technology, 2015, 37(8): 1989-1993. doi: 10.11999/JEIT141601
 Citation: Pan Sen-shan, Hu Yu-pu, Wang Bao-cang. Simpler Termination Proof on Homogeneous F5 Algorithm[J]. Journal of Electronics and Information Technology, 2015, 37(8): 1989-1993.

## Simpler Termination Proof on Homogeneous F5 Algorithm

• 摘要: 自从F5算法提出以来，出现了一批基于标签的Grbner基算法，它们使用了不同的选择策略且减少冗余多项式的准则也各不相同。为了满足正确终止性，这些算法的策略和准则必须满足一些一般的规律。根据这些规律，该文提出了一个框架，使大多数算法成为该框架的实例。随后，利用重写基的性质，得到了框架的简单正确终止证明。为了得到F5算法的简单证明，该文对F5算法的约化操作进行合理的化简。特别地，对于齐次F5算法，证明了其复杂的选择策略等价于按模序选择。这样，齐次F5算法就能看成框架的一个特例，从而得到了F5算法的简单证明。
•  [1] Buchberger B. Ein algorithmus zum auffinden der basiselemente des restklassenrings nach einem nulldimensionalen polynomideal[D]. [Ph.D. dissertation], Universitt Innsbruck, Austria, 1965. [2] 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. [3] 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. [4] Arri A and Perry J. The F5 criterion revised[J]. Journal of Symbolic Computation, 2011, 46(9): 1017-1029. [5] 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. [6] Volny F. New algorithms for computing Grbner bases[D]. [Ph.D. dissertation], Clemson University, USA, 2011. [7] 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. [8] 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. [9] 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. [10] 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. [11] Eder C. An analysis of inhomogeneous signature-based Grbner basis computations[J]. Journal of Symbolic Computation, 2013, 59(0): 21-35. [12] 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.
•  [1] 牛志华, 孔得宇.  计算有限域GF(q)上2pn-周期序列的k-错线性复杂度及其错误序列的算法, 电子与信息学报. doi: 10.11999/JEIT170972 [2] 毛可飞, 陈杰, 刘建伟.  层次身份基认证密钥协商方案的安全性分析和改进, 电子与信息学报. doi: 10.11999/JEIT151443 [3] 张习勇, 祁应红, 高光普, 李玉娟.  一种计算旋转对称布尔函数的汉明重量和非线性度的新方法, 电子与信息学报. doi: 10.11999/JEIT 150164 [4] 杨孝鹏, 马文平, 张成丽.  一种新型基于环上带误差学习问题的认证密钥交换方案, 电子与信息学报. doi: 10.11999/JEIT141506 [5] 郭瑞, 金晨辉.  低轮FOX64算法的零相关-积分分析, 电子与信息学报. doi: 10.11999/JEIT140373 [6] 严迎建, 杨昌盛, 李伟, 张立朝.  ZUC序列密码算法的选择IV相关性能量分析攻击, 电子与信息学报. doi: 10.11999/JEIT141604 [7] 潘森杉, 胡予濮, 王保仓.  基于标签的矩阵型Grbner基算法研究, 电子与信息学报. doi: 10.11999/JEIT140831 [8] 王晨旭, 李景虎, 喻明艳, 王进祥.  基于FPGA平台的Piccolo功耗分析安全性评估, 电子与信息学报. doi: 10.3724/SP.J.1146.2013.00193 [9] 付向群, 鲍皖苏, 史建红, 李发达.  基于多离散对数问题的公钥密码, 电子与信息学报. doi: 10.3724/SP.J.1146.2013.01324 [10] 沈璇, 李瑞林, 李超, 赵光耀.  SHACAL-2算法中非线性函数的差分特性及其应用, 电子与信息学报. doi: 10.3724/SP.J.1146.2013.01717 [11] 徐新龙, 韩文报.  基于减轮KASUMI的f9算法单密钥攻击, 电子与信息学报. doi: 10.3724/SP.J.1146.2012.00725 [12] 付立仕, 金晨辉.  基于仿射非正型变换的Lai-Massey模型的密码学缺陷, 电子与信息学报. doi: 10.3724/SP.J.1146.2012.01574 [13] 刘向辉, 韩文报, 权建校.  基于遗传策略的格基约化算法, 电子与信息学报. doi: 10.3724/SP.J.1146.2012.01560 [14] 熊晓雯, 魏爱国, 张智军.  构造具有良好密码学性质的旋转对称布尔函数, 电子与信息学报. doi: 10.3724/SP.J.1146.2012.00329 [15] 郭瑞, 金晨辉.  强安全可调加密方案的两个密码特性, 电子与信息学报. doi: 10.3724/SP.J.1146.2010.01110 [16] 贾艳艳, 胡予濮, 杨文峰, 高军涛.  2轮Trivium的多线性密码分析, 电子与信息学报. doi: 10.3724/SP.J.1146.2010.00334 [17] 孙银霞, 李晖, 李小青.  无证书体制下的多接收者签密密钥封装机制, 电子与信息学报. doi: 10.3724/SP.J.1146.2009.01260 [18] 张鹏, 李瑞林, 李超.  Zodiac算法新的Square攻击, 电子与信息学报. doi: 10.3724/SP.J.1146.2010.00388 [19] 金栋梁, 赵亚群.  多输出plateaued函数的性质和构造, 电子与信息学报. doi: 10.3724/SP.J.1146.2007.00907 [20] 肖皇培, 张国基.  Rijndael算法的代数方程系统改进, 电子与信息学报. doi: 10.3724/SP.J.1146.2007.00533
• 点击查看大图
##### 计量
• 文章访问数:  583
• HTML全文浏览量:  40
• PDF下载量:  267
• 被引次数: 0
##### 出版历程
• 收稿日期:  2014-06-23
• 修回日期:  2015-04-24
• 刊出日期:  2015-08-19

### 目录

/

• 分享
• 用微信扫码二维码

分享至好友和朋友圈

官方微信，欢迎关注