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

来源：电子与信息学报杂志2015年第8期北京时间：

作者：潘森杉, 胡予濮, 王保仓

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

关键词：密码学, Grbner基, 标签, F5算法, 终止证明

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