齊次F5算法的簡(jiǎn)單終止性證明

潘森杉 胡予濮 王保倉(cāng)

?

齊次F5算法的簡(jiǎn)單終止性證明

潘森杉*胡予濮 王保倉(cāng)

(西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)國(guó)家重點(diǎn)實(shí)驗(yàn)室 西安 710071)

自從F5算法提出以來(lái)，出現(xiàn)了一批基于標(biāo)簽的Gr?bner基算法，它們使用了不同的選擇策略且減少冗余多項(xiàng)式的準(zhǔn)則也各不相同。為了滿足正確終止性，這些算法的策略和準(zhǔn)則必須滿足一些一般的規(guī)律。根據(jù)這些規(guī)律，該文提出了一個(gè)框架，使大多數(shù)算法成為該框架的實(shí)例。隨后，利用重寫(xiě)基的性質(zhì)，得到了框架的簡(jiǎn)單正確終止證明。為了得到F5算法的簡(jiǎn)單證明，該文對(duì)F5算法的約化操作進(jìn)行合理的化簡(jiǎn)。特別地，對(duì)于齊次F5算法，證明了其復(fù)雜的選擇策略等價(jià)于按模序選擇。這樣，齊次F5算法就能看成框架的一個(gè)特例，從而得到了F5算法的簡(jiǎn)單證明。

密碼學(xué)；Gr?bner基；標(biāo)簽；F5算法；終止證明

1 引言

Gr?bner基與求解多元多項(xiàng)式系統(tǒng)密切相關(guān)。這一工具已應(yīng)用于很多場(chǎng)景，例如編碼理論、密碼學(xué)乃至物理、生物等自然科學(xué)領(lǐng)域。Buchberger于1965年提出了第1個(gè)Gr?bner基求解算法[1]。Faugère提出了基于線性代數(shù)的F4算法[2]和基于標(biāo)簽的F5算法[3]。盡管在文獻(xiàn)[3]中，F(xiàn)5算法的正確終止證明是錯(cuò)誤的，但F5算法仍是當(dāng)今最高效的Gr?bner基求解算法之一。其巧妙地利用標(biāo)簽去消除冗余的計(jì)算。運(yùn)用這個(gè)想法，最近幾年學(xué)者們提出了其它基于標(biāo)簽的算法：Arri-Perry(AP)[4],Gao-Guan-Volny(G2V)[5], Gao-Volny-Wang(GVW)[6]和Gao-Volny-Wang- Huang-Stroomer(GVWHS)[7]。它們都使用了Buchberger風(fēng)格，但它們似乎又與F5算法截然不同。2011年，文獻(xiàn)[8]給出了F5算法的正確性證明，并把其終止性證明留作一個(gè)公開(kāi)問(wèn)題。這一公開(kāi)問(wèn)題在文獻(xiàn)[9]中也被認(rèn)為是困難的。本文作者在文獻(xiàn)[10]中給出了齊次F5的終止性證明，但其設(shè)計(jì)的框架只適用于增量型算法，不具有一般性。通過(guò)把算法的準(zhǔn)則改寫(xiě)成二元序關(guān)系，文獻(xiàn)[11]給出了一個(gè)一般算法的簡(jiǎn)單證明。然而，它沒(méi)有解決F5的終止性問(wèn)題。為了滿足正確終止性，這些算法的策略和準(zhǔn)則必須滿足一些一般的規(guī)律。根據(jù)這些規(guī)律，本文給出了基于標(biāo)簽算法的一般框架，使得這些算法都被包含入框架之中。嚴(yán)格地說(shuō)，這一框架不是一個(gè)算法，因其部分操作沒(méi)有具體確定。本文研究這一框架的正確性和終止性，從理論上給出了一個(gè)簡(jiǎn)單證明。這就意味著，上述F5類算法的正確性和終止性都同時(shí)得到了證明。也就是說(shuō)，對(duì)于任意的多項(xiàng)式組，這一類算法都能在有限的時(shí)間內(nèi)算出正確的Gr?bner基。只要遵循框架的基本要求，設(shè)計(jì)出來(lái)的算法都正確。這一結(jié)論對(duì)于指導(dǎo)設(shè)計(jì)更高效Gr?bner基求解算法來(lái)說(shuō)是非常重要的。與文獻(xiàn)[10]的證明相比，本文利用重寫(xiě)基的性質(zhì)，極大化簡(jiǎn)了證明過(guò)程。為了得到F5算法的簡(jiǎn)單證明，本文對(duì)F5算法的約化操作進(jìn)行合理的化簡(jiǎn)。特別地，對(duì)于齊次F5算法，本文證明了其復(fù)雜的選擇策略等價(jià)于按模序選擇。這樣，齊次F5算法就能看成框架的一個(gè)特例，從而得到了F5算法的簡(jiǎn)單證明。

2 預(yù)備知識(shí)

由文獻(xiàn)[4]和文獻(xiàn)[10]的結(jié)論可得到如下的性質(zhì)。

推論1[11]令使且它們非合沖。若和都S-不可約，則。

3 框架偽代碼

表1 框架偽代碼

(12) end if

(13) end if

(14) end while

注意到，該框架有意不給出代碼第7行兩個(gè)準(zhǔn)則的具體操作，目的是使框架能包含不同版本的合沖準(zhǔn)則和重寫(xiě)準(zhǔn)則。有些算法的準(zhǔn)則不能完全去掉可重寫(xiě)或可預(yù)測(cè)的J-對(duì)。假設(shè)在某輪循環(huán)中，選出的可重寫(xiě)或可預(yù)測(cè)，即使它通過(guò)了這兩個(gè)準(zhǔn)則，本文后續(xù)的正確終止證明是不受影響的。

本文的算法1框架比文獻(xiàn)[9]的算法更簡(jiǎn)單且更有一般性，主要體現(xiàn)在以下兩方面。

(1)該框架是非遞增的，但它可以涵蓋遞增算法，只要把模序設(shè)置為索引兼容的(即這個(gè)模序最先比較兩個(gè)標(biāo)簽的索引)。

(2)盡管選擇策略在代碼第5行已經(jīng)給定，但它仍可以模擬文獻(xiàn)[9]中先選次數(shù)最低J-對(duì)的策略，只要把單項(xiàng)式序設(shè)置成次數(shù)兼容的(即這個(gè)序最先比較兩個(gè)元素的次數(shù))。詳細(xì)的模擬見(jiàn)第4節(jié)。

4 正確終止性證明

與文獻(xiàn)[10]的證明方法相似，下面將用Huang的思想來(lái)構(gòu)造向量，從而證明終止問(wèn)題。

引理4 在有限步循環(huán)之后，假設(shè)框架已經(jīng)算出S-Gr?bner基，那么該框架將會(huì)在繼續(xù)執(zhí)行有限步后終止。

下面將用歸納法證明，框架能在有限步后正確終止。這里不考慮合沖-多項(xiàng)式是因?yàn)檫@類多項(xiàng)式不能生成新的J-對(duì)。框架的正確性取決于是否能夠計(jì)算出所有的首不可約-多項(xiàng)式。

5 化簡(jiǎn)

在F5算法的約化過(guò)程中，需要檢查每一個(gè)S-約化子是否能通過(guò)兩個(gè)準(zhǔn)則，而不是像本文代碼第7行那樣，只檢查被約化的-多項(xiàng)式。本文把F5算法的約化操作叫做F5-約化。文獻(xiàn)[10]證明了“S-約化”與“F5-約化”是等價(jià)的，利用文獻(xiàn)[11]的方法，本文給出一個(gè)極其簡(jiǎn)單的等價(jià)性證明。

6 選擇策略

注意到，本文給出的偽代碼在每輪循環(huán)時(shí)，總是選擇具有最小標(biāo)簽的J-對(duì)來(lái)做約化，即按模序選取。這與GVW算法的選取策略顯然是相同的。更重要的是，下面的研究表明這種策略與文獻(xiàn)[3]和文獻(xiàn)[10]所用的策略是有相似性的。利用這一點(diǎn)，F(xiàn)5算法就能被看成前文框架的一個(gè)特例，進(jìn)而被證明正確終止。

7 非齊次輸入多項(xiàng)式

從前文的偽代碼描述里可以看出，框架可以處理非齊多項(xiàng)式，但根據(jù)上一節(jié)討論，框架不能模擬非齊F5算法的選擇策略。因?yàn)榇藭r(shí)，，選擇次數(shù)為的J-對(duì)不一定等同于選擇s-次數(shù)為的J-對(duì)。

證明 證明J-對(duì)的存在與引理3相同。與齊次輸入的情況比，框架將處理一些由突變生成的額外的J-對(duì)。由于次數(shù)不超過(guò)的-多項(xiàng)式的個(gè)數(shù)是有限的，在有限步循環(huán)后，滿足條件的J-對(duì)將被選出，從而被約化成。 證畢

參考文獻(xiàn)

[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網(wǎng)絡(luò)優(yōu)先出版

國(guó)家自然科學(xué)基金(61173151, 61173152)資助課題

潘森杉： 男，1986年生，博士生，研究方向?yàn)槎嘧兞抗€密碼、Gr?bner基.

胡予濮： 男，1955年生，博士，教授，博士生導(dǎo)師，研究方向?yàn)楦窆€密碼、流密碼等.

王保倉(cāng)： 男，1979年生，博士，副教授，碩士生導(dǎo)師，研究方向?yàn)楦窆€密碼、多變量密碼等.