齊次F5算法的簡單終止性證明

潘森杉 胡予濮 王保倉

?

齊次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年生，博士，副教授，碩士生導師，研究方向為格公鑰密碼、多變量密碼等.