基于標(biāo)簽的矩陣型Gr?bner基算法研究

潘森杉胡予濮 王保倉

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

基于標(biāo)簽的矩陣型Gr?bner基算法研究

潘森杉*胡予濮 王保倉

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

目前基于標(biāo)簽的Gr?bner基算法大多是Buchberger型的，涉及矩陣型算法的文獻(xiàn)往往是為了進(jìn)行復(fù)雜度分析，而不考慮實際的效率。該文從實際應(yīng)用出發(fā)，給出矩陣型Gao-Volny-Wang(GVW)算法的一個實例，提出算法層次的優(yōu)化設(shè)計方法。同時，該文還給出一個高效的約化準(zhǔn)則。通過實驗，該文比較了算法可用的各項準(zhǔn)則及策略。實驗結(jié)果表明，該文的矩陣型GVW實例在準(zhǔn)則和策略的選取上是最優(yōu)的。并且，矩陣型GVW在某些多項式系統(tǒng)(例如，Cyclic系列和Katsura系列多項式系統(tǒng))下比Buchberger型GVW要快2～6倍。

密碼學(xué)；Gr?bner基；標(biāo)簽；多項式；Gao-Volny-Wang (GVW)算法

1 引言

Gr?bner基是求解多元多項式系統(tǒng)的一個基本數(shù)學(xué)工具。求出了多項式組的Gr?bner基，多項式系統(tǒng)的解就能很快算出。這一工具廣泛應(yīng)用于編碼理論、密碼學(xué)乃至物理、生物等自然科學(xué)領(lǐng)域。1965年，Buchberger[1]提出了第1個Gr?bner基求解算法。1983年，為了分析Buchberger算法的復(fù)雜度，Lazard引入了線性代數(shù)的方法[2]。隨后Faugère提出了基于線性代數(shù)的F4算法[3]和基于標(biāo)簽的F5算法[4]。F4, F5算法是目前公認(rèn)的兩個高效Gr?bner基求解算法。Faugère和Joux在文獻(xiàn)[5]中使用了矩陣F5算法成功地攻破了隱藏域方程(Hidden Field Equations, HFE)公鑰密碼系統(tǒng)的第1個挑戰(zhàn)(80 bit)。雖然源碼未曾公開，文獻(xiàn)[6, 7]給出其算法的偽代碼，文獻(xiàn)[8]給出一個更詳細(xì)的矩陣算法版本。矩陣F5算法的核心思想是借鑒F4中線性代數(shù)的方法來同時約化多個多項式。但是到目前為止沒有任何文獻(xiàn)專門研究矩陣型F5和Buchberger型F5孰優(yōu)孰劣和如何設(shè)計準(zhǔn)則和策略高效實現(xiàn)矩陣型F5。唯一可以知道的是，文獻(xiàn)[9, 10]都有提及矩陣型F5一般要比F5算法要低效。

近年來涌現(xiàn)出一批基于標(biāo)簽的Gr?bner基算法，例如Arri-Perry(AP)[11], Gao-Guan-Volny(G2V)算法[12]和Gao-Volny-Wang(GVW)算法[13]。它們都使用了Buchberger風(fēng)格，但它們似乎又與F5算法截然不同。什么樣的策略和準(zhǔn)則對算法的幫助較大是一個值得研究的問題。

本文研究了矩陣型GVW算法的應(yīng)用準(zhǔn)則、策略和實現(xiàn)技巧。在設(shè)計上，為了減小約化的開銷，本文采用了延遲求模的方法。在預(yù)處理過程中，本文對Macaulay矩陣進(jìn)行并行化構(gòu)造。除此之外，還使用了一個更高效的約化準(zhǔn)則。在實現(xiàn)上，本文比較了在不同的模序、c-對選取序、重寫序下的矩陣型GVW算法的實際效果。而且，實驗得出了矩陣型GVW算法在某些多項式系統(tǒng)下要比Buchberger型GVW算法快2～6倍。最后本文還將其與突變GVW (M-GVW)算法[14]相比較，結(jié)果表明矩陣型GVW算法優(yōu)勢明顯。

2 預(yù)備知識

令R=K[x1,x2,…,xn]為域K上的n變量多項式環(huán)，M為單項式

≤記為M上的可允許單項式序。R上的一個非零多項式p能寫成關(guān)于序≤的單項式K線性組合：，其中ca∈K{0}, xa∈M, A為?n上的一個有限集。如果xb是集合{xa|a∈A}的最大單項式，那么HM(p)=xb(相應(yīng)地，HT(p)=cbxb, HC(p)=cb)叫做p關(guān)于≤的首單項式(相應(yīng)地，首項，首項系數(shù))。p的次數(shù)記為deg(p)，若p≠0其次數(shù)為，否則為-1。

令I(lǐng)為集合F={f1,f2,…,fd}∈R生成的理想，即I ={u1f1+u2f2…+udfd|u1,u2,…,ud∈R}。考慮映射：其中ei是Rd的第i個單位向量使得自由R-模Rd由集合Σ={e1,e2,…,ed}生成。本文在Md={mei|m∈M,i∈[1,d]}上定義一個模序≤s與≤適配}(見文獻(xiàn)[15, 16]): m≤t?mei≤stei。如果不產(chǎn)生歧義，≤s簡記為≤。L={(max{HM(ui)ei,≤},p)|φ(u) =p∈I}被叫作?-多項式的集合，其中u =。令α=(s,p)∈L*，其中L*=L (0,0)，第1部分s =max{HM(ui)ei,≤}叫做α的標(biāo)簽，記為S(α)，第2部分p=poly(α)是其多項式部分。不失一般性，本文假定poly(α)總是首一的。同樣，定義α的首單項式為HM(α)=HM(p)，次數(shù)為

deg(α)=deg(S(α))=max{deg(ui)} 。如果S(α)=tej，就把idx(α)=j記為其索引。s-次數(shù)(見文獻(xiàn)[17]) 定義為degs(α)=deg(S(α))+deg(fidx(α))。子集Syz= {(s,0)∈L*}叫做L的合沖子模，NS=LSyz 被叫作非合沖多項式集。令(s1,p1)和(s2,p2)是NS中的兩個非合沖?-多項式。由形如(p2s1?p1s2,0)的合沖生成的模叫做主合沖子模PS。

一個?-多項式α∈L是可預(yù)測的，如果一個Gr?bner基算法已經(jīng)找到一個合沖δ∈Syz使得S(δ)|S(α)。算法應(yīng)當(dāng)避免計算這樣的α，因此其被稱為冗余的。

α∈NS 被稱為是關(guān)于B?L*首可約的，若存在一個?-多項式β∈B滿足下列條件之一，

(1)HM(tβ)=HM(α)且S(tβ)＜S(α);

(2)S(tβ)=S(α)且HM(tβ)＜HM(α);

(3)HM(tβ)=HM(α)且S(tβ)=S(α), t∈M。

否則，α關(guān)于B首不可約。

α?t β這一操作叫做S-約化 (對應(yīng)的，M-約化，超首約化)，若滿足條件(1) (對應(yīng)的，條件(2)，條件(3))。條件(1)中，β和tβ分別被稱為S-約化子和乘性S-約化子。有時tβ也簡稱為S-約化子。令γ為用α去S-約化tβ的結(jié)果，這一過程可表示成是的自反傳遞閉包，即反復(fù)執(zhí)行約化操作直到得到一個S-不可約的?-多項式。若不考慮標(biāo)簽的大小關(guān)系，這樣的約化叫做c-約化。

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

引理1 令α為NS中的非合沖元．α是可以被L*來M-約化的，當(dāng)且僅當(dāng)它是可以被L*來S-約化的。

利用上述引理的逆否命題，本文得出如下結(jié)果。

推論1[18]令α,β∈L*使S(α)=S(β)且它們非合沖。若α和β都S-不可約，則HM(α)=HM(β)。

由文獻(xiàn)[17]可知，若α∈NS是齊次的，deg(α)=degs(α)，否則deg(α)≤degs(α)。

若α是S-不可約的且deg(α)＜degs(α)，則稱其為一個突變 (原始定義見文獻(xiàn)[19])。如果輸入多項式是齊次的，那么NS中是不存在突變的。

一個集合G?L叫做模L的S-Gr?bner基，如果任意的非合沖α∈NS能夠被G首約化。

由引理1可知，I中的每個非零多項式可以被I的Gr?bner基{poly(α)|α∈G,poly(α)≠0}約化。因此S-Gr?bner基實際上是文獻(xiàn)[11]的一個術(shù)語，它是文獻(xiàn)[20]中“強(qiáng)Gr?bner基”的精簡版。由上述定義可知，合沖?-多項式不是S-Gr?bner基的必要組成部分。本文說兩個?-多項式α和β等價，如果S(α)=S(β)且HM(α)=HM(β)。顯然，所有的非合沖首不可約?-多項式組成具有最少個數(shù)的S-Gr?bner基。文獻(xiàn)[11]，文獻(xiàn)[21]和文獻(xiàn)[16]指出，非合沖不可約?-多項式只有有限多個(不計等價)。

3 重寫序

本文引入文獻(xiàn)[18]中定義在G上的關(guān)于重寫準(zhǔn)則的概念。一個?-多項式α∈G是標(biāo)簽s的重寫子，如果α是G中使得S(tα)=s的-最大元素，其中t∈M,為G上一個線性序(稱為重寫序)。與文獻(xiàn)[18]相比，這里對沒有過多的限制：它只要是G上的線性序即可。有時本文也把tα叫做s的重寫子。mβ∈M×G 是可重寫的，如果S(mβ)的重寫子是α≠β?，F(xiàn)在用的最多的是兩種重寫序是文獻(xiàn)[18]中的r和文獻(xiàn)[4]Rules集合中元素的排序(記為new)。它們的定義如下：

令α,β∈NS ,Γαβ記為最小公倍數(shù)lcm(HM(α), HM(β))。令mα=且。若r(α)＞r(β), mαα在文獻(xiàn)[13]中被稱為α和β的J-對。(α,β)叫做c-對，deg(Γαβ)叫做c-對(α,β)的(全)次數(shù)。r(α)＞r(β)時，degs(mαα)叫做c-對的s-次數(shù)。

4 矩陣型Gr?bner基算法

首先，本文引入文獻(xiàn)[18]中關(guān)于重寫基的一些術(shù)語。G是標(biāo)簽s的重寫基，如果s的重寫子tα∈M×G 不是S-可約化的。對于所有小于s的標(biāo)簽s'，如果G是標(biāo)簽s'的重寫基，那么G被稱為直到s的重寫基(記為G)。?-多項式集L＜s的S-Gr?bner基也可以記為G。記號G和G有類似的定義。

G，如果α是首不可約?-多項式且S(α)＜s，則G中有另一?-多項式與α等價。

證明略。

為了與文獻(xiàn)[14]的M-GVW算法作比較，這里假設(shè)e1＞e2…＞ed。與文獻(xiàn)[22]一樣，本文可以推導(dǎo)出e1,e2,…,ed為首不可約標(biāo)簽。

給定一組多項式，矩陣型GVW算法求出其理想的Gr?bner基，其中，sort(F,≤) (相應(yīng)地，min(F,≤)) 表示按序“≤”排列 (相應(yīng)地，選取)集合F中的元素。顧名思義，cpair(α,β) 為α 和β組成的c-對。spoly(α,β) 表示α 和β 的s-多項式mαα?mββ, concat(A,B)的意思是把集合B中的元素排到集合A的后面。子算法S-REDUCE利用G來反復(fù)s-約化?-多項式組V，記錄下具有新的首項的不可約?-多項式。對于?-多項式組V的所有單項式，子算法SYMBOLIC_PREPROCESS的目的是尋找滿足準(zhǔn)則的c-約化子。如果將這些約化子的系數(shù)分別寫進(jìn)矩陣的各行，本文就構(gòu)造出了Macaulay矩陣。

這里不給出矩陣型GVW算法，因其偽代碼與文獻(xiàn)[14]基本相同，本節(jié)將著重介紹對其子算法的改進(jìn)及優(yōu)化。

與矩陣型算法相對應(yīng)的是Buchberger型算法，即算法每次只選擇一個c-對。對于計算S-Gr?bner基的算法，文獻(xiàn)[13]的實驗得出兩個高效的模序，記為≤POT(位置先于項)和≤SR(Schreyer 見文獻(xiàn)[23])，它們的定義如下：

mei≤POTtej，如果i＜j，或者i=j, m≤t，其中m,t∈M。

mei≤SRtej，如果HM(mfi)＜HM(tfj)，或者HM(mfi)=HM(tfj), i＜j。

矩陣型GVW算法的正確終止性證明可利用推論2，對標(biāo)簽s進(jìn)行數(shù)學(xué)歸納得到，細(xì)節(jié)可以參見文獻(xiàn)[13, 14]，這里不再贅述。本節(jié)主要討論算法的優(yōu)化設(shè)計，部分方法借鑒了Fayssal Martani對矩陣F4算法的優(yōu)化實現(xiàn)。

4.1 延遲求模

約化操作是Gr?bner基算法中開銷最大的部分，當(dāng)基域較小時，每次約化后多項式系數(shù)都要作求模操作。一個自然的想法就是延遲求模運(yùn)算，即S-約化得到S-不可約多項式之后再對各多項式求模。這一技巧能加速計算Gr?bner基，特別是當(dāng)基域是F2的時候。算法S-REDUCE用H來記錄s-約化為零的那些合沖組成的子模。

4.2 高效約化準(zhǔn)則

注意到，在選取tβ的時候，通常的做法是確保tβ的標(biāo)簽為非合沖的，并且使tβ不能被重寫。實際上，如果算法檢查每個S-約化子是否滿足這兩個準(zhǔn)則，那么算法的效率是相當(dāng)?shù)拖碌摹Ｋ员疚慕o出了一個等價但更高效的準(zhǔn)則：?-多項式β的一個S-約化子tβ被稱為最小乘性S-約化子，如果

(1)S(tβ)是所有S-約化子中最小的標(biāo)簽；

(2)若有多個S-約化子滿足條件1，選取S(β)最大的一個。

事實1 令α∈L*, G為G。對于矩陣型GVW算法，α的S-約化子tβ通過合沖和重寫準(zhǔn)則當(dāng)且僅當(dāng)其是最小乘性S-約化子。

鑒于篇幅，本文給出其證明思路：證明其逆否命題的充分和必要性。

4.3 并行構(gòu)造Macaulay矩陣

與文獻(xiàn)[14]相同的是，子算法SYMBOLIC_ PREPROCESS函數(shù)不指定s的選取先后順序。這樣的好處是可以對該函數(shù)進(jìn)行并行化處理。程序使用了Inter TBB (Thread Building Blocks)庫來實現(xiàn)這一操作。具體來說，在構(gòu)造Macaulay矩陣的時候(即把多項式集合寫成||×|T|的矩陣，一行代表中的一個多項式，其中列元素記錄了該多項式關(guān)于T的系數(shù))，本文用多個線程將中不同多項式寫成矩陣的行向量，如線程1當(dāng)前處理的單項式在THM()中，則線程1得到互斥鎖，處理完一個單項式后再釋放互斥鎖。鑒于篇幅，本文省略算法的具體流程。

5 實驗數(shù)據(jù)

本文代碼是基于Mathicgb庫[24]的C++實現(xiàn)。硬件平臺為Intel Core i3 2.40 GHz，運(yùn)行環(huán)境為64-bit Ubuntu 14.04操作系統(tǒng)?；驗镕32003，單項式序為≤DRL。為了檢驗線性代數(shù)方法對于Gr?bner基算法是否有加速作用，本文對矩陣型和Buchberger型GVW算法進(jìn)行實驗比較。表1～表4中，矩陣型GVW算法使用了≤SR模序，SD(按s-次數(shù)排列c-對)，重寫序為r。實驗顯示，線性代數(shù)方法對Cyclic系列和Katsura系列多項式系統(tǒng)能加速2～6倍，但該技術(shù)不具有普適性。例如GVW算法能在不到2 s的時間內(nèi)求出Jason210多項式系統(tǒng)的Gr?bner基，而矩陣型GVW算法在45 min內(nèi)都不能算出結(jié)果。

表2可以看出矩陣版本需要消耗更多的內(nèi)存，這是由于把多項式集合V存儲成Macaulay矩陣的開銷很大，盡管本文已經(jīng)使用了稀疏矩陣作為其存儲結(jié)構(gòu)。

表1 運(yùn)行時間(s)

表2 內(nèi)存占用情況 (MB)

除了上節(jié)偽代碼所描述的矩陣型算法外，本文還實現(xiàn)了基于其它策略或準(zhǔn)則的矩陣型算法。例如，表3第3列是使用F5算法的重寫準(zhǔn)則：選取G中最新的S-約化子。顯然，在實現(xiàn)上new比r(第2列)要稍快。實驗結(jié)果顯示，對于Cyclic系列和Eco系列方程組，new比r要差的多。對于Katsura系列多項式系統(tǒng)，new只需要在r下一半的運(yùn)行時間。這一特殊情況是由于算法關(guān)于兩個重寫序所算出的S-Gr?bner基是相同，并且由表4可知r需要更多的約化操作。

表3 矩陣型算法運(yùn)行時間(s)

表3第4列表示算法矩陣型GVW按照全次數(shù)從小到大的順序來選取c-對。文獻(xiàn)[3]表示，TD對于F4算法比SD要高效。然而，對于基于標(biāo)簽的Gr?bner基算法，本文的實驗結(jié)果說明了這一論斷是不成立的。

表3第5列是算法用了模序≤POT而不是≤SR的結(jié)果。需要注意的是，在排列c-對時算法仍然使用SD，這樣一來，每一個Macaulay矩陣就能包含盡可能多的多項式。表格第6列是文獻(xiàn)[14]中的矩陣型M-GVW算法，其模序為≤POT，按TD選取c-對。M-GVW使用了一個新的策略：如果算法計算出一個突變，則將其c-約化后賦以新的標(biāo)簽。也就是說，算法將其看成一個新的輸入多項式。這樣，新的?-多項式在已算出的G中是關(guān)于模序最小的，算法就不會因為其它準(zhǔn)則來丟掉與突變相關(guān)的c-對。注意，M-GVW只對次數(shù)小于某一常數(shù)的突變進(jìn)行處理，而在文獻(xiàn)[14]中沒有給出這一常數(shù)的具體值。所以本文在實現(xiàn)矩陣型M-GVW的時候只對算法找到的第1個突變重賦標(biāo)簽。這樣做的目的是確保M-GVW不會像文獻(xiàn)[14]所說的那樣降低性能，然而運(yùn)行結(jié)果出乎意料：M-GVW計算表3的多項式系統(tǒng)要比≤POT還要差些。從表3可以得出，無論是≤POT還是矩陣型M-GVW，它們在計算Gr?bner基的效果上都比矩陣型GVW要差。

綜上所述，本文所實例化的矩陣型GVW算法是權(quán)衡了各項準(zhǔn)則及策略的實現(xiàn)，具有相當(dāng)?shù)膶嵱眯?。找到一個對所有多項式系統(tǒng)都行之有效的算法是相當(dāng)困難的，即使是F4和F5算法也做不到。因此，怎樣設(shè)計更好更快的Gr?bner基算法的研究是值得繼續(xù)研究的問題。

表4 約化總步數(shù)

[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] Lazard D. Gr?bner-bases, Gaussian elimination and resolution of systems of algebraic equations[C]. Proceedings of the European Computer Algebra Conference on Computer Algebra, London, UK, 1983: 146-156.

[3] Faugère J C. A new efficient algorithm for computing Gr?bner bases (F4)[J]. Journal of Pure and Applied Algebra, 1999, 139(1-3): 61-88.

[4] 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.

[5] Faugère J C and Joux A. Algebraic cryptanalysis of hidden field equation (HFE) cryptosystems using Gr?bner bases[C]. Proceedings of the Advances in Cryptology-CRYPTO 2003, Springer Berlin Heidelberg, Santa Barbara, USA, 2003, 2729: 44-60.

[6] Bardet M. étude des systèmes algébriques surdéterminés. applications aux codes correcteurs et à la cryptographie[D]. [Ph.D. dissertation], Université Pierre et Marie Curie-Paris VI, 2004.

[7] Faugère J C and Rahmany S. Solving systems of polynomial equations with symmetries using SAGBI-Gr?bner bases[C]. Proceedings of the 34th International Symposium on Symbolic and Algebraic Computation, New York, USA, 2009: 151-158.

[8] Albrecht M and Perry J. F4/5[OL]. http:// adsabs. harvard. edu/abs/2010arXiv1006.4933A. 2010.

[9] Faugère J C, Safey El Din M, and Verron T. On the complexity of computing Gr?bner bases for quasihomogeneous systems[C]. Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, New York, USA, 2013: 189-196.

[10] Bardet M, Faugère J C, and Salvy B. On the complexity of the F5 Gr?bner basis algorithm[OL]. http://arxiv.org/abs/ 1312.1655. 2013.

[11] Arri A and Perry J. The F5 criterion revised[J]. Journal of Symbolic Computation, 2011, 46(9): 1017-1029.

[12] 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.

[13] 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.

[14] Sun Yao, Lin Dong-dai, and Wang Ding-kang. An improvement over the GVW algorithm for inhomogeneous polynomial systems[OL]. http://arxiv.org/abs/1404.1428. 2014.

[15] Huang Lei. A new conception for computing Gr?bner basis and its applications[OL]. http://arxiv.org/abs/1012.5425. 2010.

[16] 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.

[17] Eder C. An analysis of inhomogeneous signature-based Gr?bner basis computations[J]. Journal of Symbolic Computation, 2013, 59(0): 21-35.

[18] 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.

[19] Ding Jin-tai, Cabarcas D, Schmidt D, et al.. Mutant Gr?bner basis algorithm[C]. Proceedings of the 1st International Conference on Symbolic Computation and Cryptography, Beijing, China, 2008: 23-32.

[20] 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.

[21] 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.

[22] Volny F. New algorithms for computing Gr?bner bases[D]. [Ph.D. dissertation], Clemson University, 2011.

[23] Greuel G M and Pfister G. A Singular Introduction to Commutative Algebra[M]. New York: Springer Berlin Heidelberg, 2008: 161-162.

[24] Roune B H and Stillman M. Practical Gr?bner basis computation[C]. Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation, New York, USA, 2012: 203-210.

潘森杉： 男，1986年生，博士生，研究方向為多變量公鑰密碼、Gr?bner基.

胡予濮： 男，1955年生，博士，博士生導(dǎo)師，教授，研究方向為格公鑰密碼、流密碼等.

王保倉： 男，1979年生，博士，碩士生導(dǎo)師，副教授，研究方向為格公鑰密碼、多變量密碼等.

Research on Signature-based Gr?bner Basis Algorithms in Matrix Style

Pan Sen-shan Hu Yu-pu Wang Bao-cang
(State Key Laboratory of Integrated Service Networks, Xidian University, Xi'an 710071, China)

The current signature-based Gr?bner basis algorithms are mostly in Buchberger style and the researches related to matrix style often aim to analyze the complexity of algorithms. From a practical aspect, this paper provides a concrete Gao-Volny-Wang (GVW) algorithm in matrix style and presents optimization at the algorithmic level. Meanwhile, an efficient reduction criterion is given in the paper. Many popular criteria and strategies are compared by some experiments which show that the matrix version described in the paper is a combination of reasonable criteria and strategies. Moreover, the matrix-GVW is two to six times faster than the Buchberger style for some polynomial systems, e.g. Cyclic series and Katsura series.

Cryptography; Gr?bner basis; Signature; Polynomial; Gao-Volny-Wang (GVW) algorithm

TP309

： A

：1009-5896(2015)04-0881-06

10.11999/JEIT140831

2014-06-23收到，2014-11-02改回

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

*通信作者：潘森杉 pansenshan@gmail.com