齐次F5算法的简单终止性证明
2015-10-13潘森杉胡予濮王保仓
潘森杉 胡予濮 王保仓
齐次F5算法的简单终止性证明
潘森杉*胡予濮 王保仓
(西安电子科技大学综合业务网国家重点实验室 西安 710071)
自从F5算法提出以来，出现了一批基于标签的Gröbner基算法，它们使用了不同的选择策略且减少冗余多项式的准则也各不相同。为了满足正确终止性，这些算法的策略和准则必须满足一些一般的规律。根据这些规律，该文提出了一个框架，使大多数算法成为该框架的实例。随后，利用重写基的性质，得到了框架的简单正确终止证明。为了得到F5算法的简单证明，该文对F5算法的约化操作进行合理的化简。特别地，对于齐次F5算法，证明了其复杂的选择策略等价于按模序选择。这样，齐次F5算法就能看成框架的一个特例，从而得到了F5算法的简单证明。
密码学；Gröbner基；标签；F5算法；终止证明
1 引言
Gröbner基与求解多元多项式系统密切相关。这一工具已应用于很多场景，例如编码理论、密码学乃至物理、生物等自然科学领域。Buchberger于1965年提出了第1个Gröbner基求解算法[1]。Faugère提出了基于线性代数的F4算法[2]和基于标签的F5算法[3]。尽管在文献[3]中，F5算法的正确终止证明是错误的，但F5算法仍是当今最高效的Gröbner基求解算法之一。其巧妙地利用标签去消除冗余的计算。运用这个想法，最近几年学者们提出了其它基于标签的算法：Arri-Perry(AP)[4],Gao-Guan-Volny(G2V)[5], Gao-Volny-Wang(GVW)[6]和Gao-Volny-Wang- Huang-Stroomer(GVWHS)[7]。它们都使用了Buchberger风格，但它们似乎又与F5算法截然不同。2011年，文献[8]给出了F5算法的正确性证明，并把其终止性证明留作一个公开问题。这一公开问题在文献[9]中也被认为是困难的。本文作者在文献[10]中给出了齐次F5的终止性证明，但其设计的框架只适用于增量型算法，不具有一般性。通过把算法的准则改写成二元序关系，文献[11]给出了一个一般算法的简单证明。然而，它没有解决F5的终止性问题。为了满足正确终止性，这些算法的策略和准则必须满足一些一般的规律。根据这些规律，本文给出了基于标签算法的一般框架，使得这些算法都被包含入框架之中。严格地说，这一框架不是一个算法，因其部分操作没有具体确定。本文研究这一框架的正确性和终止性，从理论上给出了一个简单证明。这就意味着，上述F5类算法的正确性和终止性都同时得到了证明。也就是说，对于任意的多项式组，这一类算法都能在有限的时间内算出正确的Gröbner基。只要遵循框架的基本要求，设计出来的算法都正确。这一结论对于指导设计更高效Gröbner基求解算法来说是非常重要的。与文献[10]的证明相比，本文利用重写基的性质，极大化简了证明过程。为了得到F5算法的简单证明，本文对F5算法的约化操作进行合理的化简。特别地，对于齐次F5算法，本文证明了其复杂的选择策略等价于按模序选择。这样，齐次F5算法就能看成框架的一个特例，从而得到了F5算法的简单证明。
2 预备知识
由文献[4]和文献[10]的结论可得到如下的性质。
推论1[11]令使且它们非合冲。若和都S-不可约，则。
3 框架伪代码
表1 框架伪代码
(12) end if
(13) end if
(14) end while
注意到，该框架有意不给出代码第7行两个准则的具体操作，目的是使框架能包含不同版本的合冲准则和重写准则。有些算法的准则不能完全去掉可重写或可预测的J-对。假设在某轮循环中，选出的可重写或可预测，即使它通过了这两个准则，本文后续的正确终止证明是不受影响的。
本文的算法1框架比文献[9]的算法更简单且更有一般性，主要体现在以下两方面。
(1)该框架是非递增的，但它可以涵盖递增算法，只要把模序设置为索引兼容的(即这个模序最先比较两个标签的索引)。
(2)尽管选择策略在代码第5行已经给定，但它仍可以模拟文献[9]中先选次数最低J-对的策略，只要把单项式序设置成次数兼容的(即这个序最先比较两个元素的次数)。详细的模拟见第4节。
4 正确终止性证明
与文献[10]的证明方法相似，下面将用Huang的思想来构造向量，从而证明终止问题。
引理4 在有限步循环之后，假设框架已经算出S-Gröbner基，那么该框架将会在继续执行有限步后终止。
下面将用归纳法证明，框架能在有限步后正确终止。这里不考虑合冲-多项式是因为这类多项式不能生成新的J-对。框架的正确性取决于是否能够计算出所有的首不可约-多项式。
5 化简
在F5算法的约化过程中，需要检查每一个S-约化子是否能通过两个准则，而不是像本文代码第7行那样，只检查被约化的-多项式。本文把F5算法的约化操作叫做F5-约化。文献[10]证明了“S-约化”与“F5-约化”是等价的，利用文献[11]的方法，本文给出一个极其简单的等价性证明。
6 选择策略
注意到，本文给出的伪代码在每轮循环时，总是选择具有最小标签的J-对来做约化，即按模序选取。这与GVW算法的选取策略显然是相同的。更重要的是，下面的研究表明这种策略与文献[3]和文献[10]所用的策略是有相似性的。利用这一点，F5算法就能被看成前文框架的一个特例，进而被证明正确终止。
7 非齐次输入多项式
从前文的伪代码描述里可以看出，框架可以处理非齐多项式，但根据上一节讨论，框架不能模拟非齐F5算法的选择策略。因为此时，，选择次数为的J-对不一定等同于选择s-次数为的J-对。
证明 证明J-对的存在与引理3相同。与齐次输入的情况比，框架将处理一些由突变生成的额外的J-对。由于次数不超过的-多项式的个数是有限的，在有限步循环后，满足条件的J-对将被选出，从而被约化成。 证毕
参考文献
[1] Buchberger B. Ein algorithmus zum auffinden der basiselemente des restklassenrings nach einem nulldimensionalen polynomideal[D]. [Ph.D. dissertation], Universität Innsbruck, Austria, 1965.
[2] Faugère J C. A new efficient algorithm for computing Gröbner bases (F4)[J]., 1999, 139(1-3): 61-88.
[3] Faugère J C. A new efficient algorithm for computing Gröbner 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].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] Gao Shu-hong, Volny F, and Wang Ming-sheng. A new algorithm for computing Gröbner bases[OL]. http://www. math.clemson.edu/~sgao/papers/gvw_R130704.pdf, 2010.
[7] Volny F. New algorithms for computing Gröbner bases[D]. [Ph.D. dissertation], Clemson University, USA, 2011.
[8] Sun Yao and Wang Ding-kang. A generalized criterion for signature related Gröbner basis algorithms[C]. Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation, New York, USA, 2011: 337-344.
[9] Eder C and Perry J. Signature-based algorithms to compute Gröbner bases[C]. Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation, New York, USA, 2011: 99-106.
[10] 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.
[11] Eder C and Roune B H. Signature rewriting in Gröbner basis computation[C]. Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, New York, USA, 2013: 331-338.
[12] Huang Lei. A new conception for computing Gröbner basis and its applications[OL]. http://arxiv.org/abs/1012.5425. 2010.
[13] Eder C. An analysis of inhomogeneous signature-based Gröbner basis computations[J]., 2013, 59(0): 21-35.
[14] Ding Jin-tai, Cabarcas D, Schmidt D,.. Mutant Gröbner basis algorithm[C]. Proceedings of the 1st International Conference on Symbolic Computation and Cryptography, Beijing, China, 2008: 23-32.
Simpler Termination Proof on Homogeneous F5 Algorithm
Pan Sen-shan Hu Yu-pu Wang Bao-cang
(,,710071,)
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; Gröbner basis; Signature; F5 algorithm; Termination proof
TP309
A
1009-5896(2015)08-1989-05
10.11999/JEIT141601
潘森杉 pansenshan@gmail.com
2014-06-23收到，2015-04-24改回，2015-06-08网络优先出版
国家自然科学基金(61173151, 61173152)资助课题
潘森杉： 男，1986年生，博士生，研究方向为多变量公钥密码、Gröbner基.
胡予濮： 男，1955年生，博士，教授，博士生导师，研究方向为格公钥密码、流密码等.
王保仓： 男，1979年生，博士，副教授，硕士生导师，研究方向为格公钥密码、多变量密码等.
