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

摘要：

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

关键词：密码学、Gr?bner基、标签、F5算法、终止证明

分类号：TP309(计算技术、计算机技术)

资助基金：国家自然科学基金61173151,61173152资助课题

在线出版日期：2015-09-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：1989-1993