孫澤昊, 王中孝, 趙肖鑫, 鄭群雄

戰(zhàn)略支援部隊(duì)信息工程大學(xué), 鄭州 450001

1 引言

序列密碼作為對(duì)稱密碼的重要分支之一, 不僅在軍事上扮演著重要角色, 它還在外交、政府以及商業(yè)領(lǐng)域起著至關(guān)重要的作用, 比如GSM 中的A5/1[1]、WEP 中的RC4[2]、藍(lán)牙中的E0[3]、3GPP 中的Snow 3G[4]和ZUC[5]以及面向5G 應(yīng)用場(chǎng)景設(shè)計(jì)的Snow V[6]和Snow VI[7]等都是序列密碼算法.

隨著密碼分析技術(shù)的發(fā)展, 序列密碼的設(shè)計(jì)已經(jīng)進(jìn)入非線性驅(qū)動(dòng)的時(shí)代. 非線性反饋移位寄存器(nonlinear feedback shift registers, NFSRs) 是一類重要的非線性序列生成器, 在序列密碼中廣泛使用,例如歐洲序列密碼計(jì)劃eSTREAM 項(xiàng)目最終勝選的兩個(gè)算法Grain[8]和Trivium[9]都使用NFSR 作為重要部件, 其中Trivium 在2012 年成為國(guó)際標(biāo)準(zhǔn)密碼算法.

串聯(lián)結(jié)構(gòu)是NFSRs 的一種重要結(jié)構(gòu)模型, 它是1970 年由美國(guó)學(xué)者Green 等人[10]首次提出的. 通過引入布爾函數(shù)的星積運(yùn)算(也稱?運(yùn)算), Green 等人證明了以f1(x0,x1,··· ,xn) 為特征函數(shù)的NFSR串聯(lián)到以f2(x0,x1,··· ,xn) 為特征函數(shù)的NFSR 和以f1?f2為特征函數(shù)的NFSR 生成相同的序列簇.對(duì)設(shè)計(jì)者而言, 串聯(lián)結(jié)構(gòu)可以有效地控制NFSR 的電路深度和輸出序列的周期. 例如, Grain v1 算法采用80 級(jí)本原線性反饋移位寄存器(linear feedback shift register, LFSR) 來控制80 級(jí)NFSR, 使得輸出序列的周期都是280?1 的倍數(shù). 對(duì)攻擊者而言, 更關(guān)心的是NFSR 的串聯(lián)分解問題, 即能否將一個(gè)較大級(jí)數(shù)的NFSR 分解為兩個(gè)級(jí)數(shù)較小的NFSR 的串聯(lián), 通過結(jié)構(gòu)的等價(jià)變形來有效降低攻擊的復(fù)雜度. 例如當(dāng)存在分解h=f ?g, 且f不含常數(shù)項(xiàng)1 時(shí), 在某些狀態(tài)下以h為特征函數(shù)的NFSR 就退化為以g為特征函數(shù)的NFSR, 特別地, 當(dāng)g是線性布爾函數(shù)時(shí), 這種退化可能會(huì)導(dǎo)致非常有效的攻擊方法, 從而大大削弱相應(yīng)算法的安全性.

然而, 如何將一個(gè)NFSR 分解為兩個(gè)級(jí)數(shù)更小的NFSR 的串聯(lián)是一個(gè)富有挑戰(zhàn)性的問題. 到目前為止僅對(duì)某些特殊情形有高效的分解算法, 而對(duì)一般情形的分解算法仍有待進(jìn)一步研究. NFSR 的串聯(lián)分解首先在文獻(xiàn)[11] 中研究, 它給出了一種特例, 即右線性星積分解, 可以將特征函數(shù)h分解為f ?l, 其中l(wèi)是線性布爾函數(shù). 但是由于這種分解算法只利用了最高次項(xiàng)中部分項(xiàng)的信息, 故它得到的候選集并不精確.文獻(xiàn)[12] 中給出了右線性星積分解的等價(jià)條件, 同時(shí)給出了一種改進(jìn)算法, 因?yàn)楦倪M(jìn)算法利用了所有最高次項(xiàng)的信息, 所以得到了更精確的候選集. 文獻(xiàn)[13] 在總結(jié)梳理上述兩種方法的基礎(chǔ)上, 給出了更加具有一般性的高階差分的方法, 可用于進(jìn)一步縮小候選集的范圍. 文獻(xiàn)[13] 也給出了左線性星積分解的高效算法, 得到了很好的結(jié)果, 能夠直接求解最大階左線性星積因子. 更重要的是, 文獻(xiàn)[13] 還給出了NFSR 的非線性串聯(lián)分解算法, 但算法實(shí)現(xiàn)較為復(fù)雜, 對(duì)計(jì)算和存儲(chǔ)都有很高的要求, 對(duì)小規(guī)模的NFSR 可以有效分解, 但當(dāng)級(jí)數(shù)較大時(shí)分解算法仍有待進(jìn)一步優(yōu)化和改進(jìn).

此外, 關(guān)于NFSR 串聯(lián)分解的唯一性, 也有學(xué)者進(jìn)行了研究. 文獻(xiàn)[13] 證明了最大階的左線性星積因子是唯一的; 文獻(xiàn)[14] 證明了最大階的右線性星積因子也是唯一的, 并且舉例說明, 在一般情形下, NFSR的串聯(lián)分解未必唯一; 文獻(xiàn)[15] 在研究NFSR 串聯(lián)分解唯一性的基礎(chǔ)上, 給出了當(dāng)一個(gè)NFSR 既存在右線性星積因子分解,又存在左線性星積因子分解時(shí),兩種分解方式的內(nèi)在聯(lián)系; 文獻(xiàn)[16]研究了Grain-like結(jié)構(gòu)串聯(lián)分解的唯一性, 并證明了Grain v1、Grain-128、Grain-128a 三個(gè)算法中驅(qū)動(dòng)寄存器的串聯(lián)分解是唯一的.

從目前已有結(jié)果來看, 對(duì)于給定的特征函數(shù)h=f ?g, 其中f和g是兩個(gè)非線性特征函數(shù), 想要由h分解出f和g并非易事. 考慮到對(duì)于隨機(jī)給定的兩個(gè)大素?cái)?shù)p和q, 如果p,q較為接近, 也即|p ?q| 較小, 則可以利用費(fèi)馬因子分解方法[17]由N=pq有效地分解出p和q. 特別是當(dāng)p=q時(shí), 還可用快速整數(shù)開方算法[18]求出p. 那么對(duì)于特征函數(shù), 是否也有類似情形呢? 即當(dāng)f和g較為“接近” 時(shí), 甚至當(dāng)f=g時(shí), 是否存在由h=f ?g分解出f和g的高效算法呢? 本文我們研究上述特殊情形的星積分解問題, 以期能為一般的星積分解問題提供借鑒和探索分解之法. 首先, 本文給出h=g ?g的兩個(gè)必要條件. 隨后, 基于對(duì)布爾函數(shù)“求偏導(dǎo)” (定義見第2.1 節(jié)) 的思想給出兩種情形下由h=g ?g求解g的高效算法, 并給出算法的時(shí)間復(fù)雜度分析. 與文獻(xiàn)[13] 中算法相比, 本文的算法在時(shí)間復(fù)雜度方面有明顯優(yōu)勢(shì).最后, 本文從星積分解的角度給出了兩個(gè)特征函數(shù)較為“接近” 的一種刻畫, 并將兩個(gè)較為“接近” 的特征函數(shù)的星積分解問題轉(zhuǎn)化為h=g ?g的星積分解問題. 此外, 上述結(jié)論也可以拓展至h=g ?g ?···?g的星積分解.

本文后續(xù)章節(jié)安排如下: 第2 節(jié)給出本文所需的預(yù)備知識(shí); 第3 節(jié)給出本文的主要結(jié)果, 即關(guān)于h=g ?g的星積分解理論以及星積分解算法; 第4 節(jié)首先給出h=g ?g的另一種求偏導(dǎo)方式的結(jié)果, 接著將一類非線性星積分解問題轉(zhuǎn)化為h=g ?g的星積分解問題, 最后進(jìn)一步研究了h=g ?g ?···?g的星積分解問題; 第5 節(jié)對(duì)本文進(jìn)行總結(jié), 并提出有待進(jìn)一步研究的問題.

2 準(zhǔn)備知識(shí)

記“⊕” 為異或加; “+” 為一般的整數(shù)加法; “·” 為一般的多項(xiàng)式乘法. 設(shè)k ∈R, 記「k?為大于等于k的最小整數(shù),?k」為小于等于k的最大整數(shù).

2.1 布爾函數(shù)

設(shè)n是正整數(shù), 一個(gè)n元布爾函數(shù)為二元域F2上的n維向量空間Fn2到F2上的一個(gè)映射. 記全體n元布爾函數(shù)構(gòu)成的集合為Bn. 對(duì)f ∈Bn, 其可以唯一地表示為如下形式:

并記T(f) 中所有變?cè)淖畲笙聵?biāo)與最小下標(biāo)分別為ord(f) 與minsub(f), 其中ord(f) 通常稱為f的階.

設(shè)f(x0,x1,··· ,xn?1)∈Bn, 則f關(guān)于變?cè)獂i可唯一地表示為如下形式

令h=f ?g, 則h ∈Bn+m+1. 值得注意的是, 星積運(yùn)算通常不可交換, 即f ?g ?=g ?f. 稱f為h的左星積因子,g為h的右星積因子. 根據(jù)上述定義, 易知命題1成立.

命題1設(shè)f,g,h為三個(gè)布爾函數(shù), 則

其中?為全體線性布爾函數(shù)到單變?cè)囗?xiàng)式環(huán)F2[x] 的一一映射. 進(jìn)一步, 記??1為?的逆, 可知

設(shè)f,g是線性布爾函數(shù), 容易驗(yàn)證

2.2 非線性反饋移位寄存器

一個(gè)n級(jí)Fibonacci 型非線性反饋移位寄存器(簡(jiǎn)稱NFSR) 如圖1 所示.

圖1 n 級(jí)Fibonacci 型非線性反饋移位寄存器Figure 1 n-stage Fibonacci NFSR

其中f0∈Bn稱為其反饋函數(shù). 特別地, 若f0是線性的, 則稱該NFSR 為線性反饋移位寄存器(簡(jiǎn)稱LFSR). 給定NFSR 的一個(gè)初態(tài)(a0,a1,··· ,an?1)∈, 其輸出序列(a0,a1,···)∈滿足n階遞歸關(guān)系式

令

稱f為該NFSR 的特征函數(shù), 并記該NFSR 為NFSR(f). 遍歷2n個(gè)初態(tài), NFSR(f) 可以生成2n條不同的序列, 稱這些序列構(gòu)成的集合為NFSR(f) 生成的序列簇, 記作G(f). 進(jìn)一步, 若G(f) 中的序列均是周期的, 則稱NFSR(f) 是非奇異的. 文獻(xiàn)[19] 證明了NFSR(f) 是非奇異的當(dāng)且僅當(dāng)f可寫作如下形式:

稱形如式(1)的任一布爾函數(shù)為一個(gè)n階非奇異特征函數(shù). 記C為全體非奇異特征函數(shù)構(gòu)成的集合, 記C?={f ∈C|f(0)=0}.

設(shè)f=f0(y0,y1,··· ,yn?1)⊕yn, g=g0(x0,x1,··· ,xm?1)⊕xm分別為兩個(gè)NFSR 的特征函數(shù).如圖2 所示為NFSR(f) 到NFSR(g) 的串聯(lián)結(jié)構(gòu), 記作NFSR(f,g). 最左端寄存器為該裝置的輸出端, 其輸出的全體序列構(gòu)成的集合為G(f,g). 文獻(xiàn)[10] 證明了NFSR(f,g) 的輸出實(shí)際上等價(jià)于一個(gè)m+n級(jí)NFSR(h) 的輸出, 即G(f,g) =G(h), 其中后者的特征函數(shù)h=f ?g. 這一結(jié)論表明對(duì)NFSR 串聯(lián)結(jié)構(gòu)的研究本質(zhì)上可以轉(zhuǎn)化為對(duì)布爾函數(shù)星積性質(zhì)的研究. 進(jìn)一步, 文獻(xiàn)[12] 證明了NFSR(h) 是非奇異的,當(dāng)且僅當(dāng)NFSR(f) 與NFSR(g) 均是非奇異的, 即

圖2 NFSR(f) 到NFSR(g) 的串聯(lián)Figure 2 Cascade connection of NFSR(f) into NFSR(g)

命題2[12]設(shè)h=f ?g, 則h ∈C當(dāng)且僅當(dāng)f,g ∈C.

2.3 左線性星積分解

命題3[13]給定h,g ∈C?, 若存在f1,f2∈C?使得h=f1?g=f2?g, 則f1=f2.

命題3說明, 給定h的右星積因子時(shí),h的左星積因子是唯一的.

設(shè)h ∈C?, 稱如下集合

為h的標(biāo)準(zhǔn)項(xiàng)集合(standard term set). 對(duì)任意給定的h ∈C?,h可唯一表示為

其中l(wèi)t是由h和t唯一確定的線性布爾函數(shù). 稱式(2)為h的標(biāo)準(zhǔn)項(xiàng)表示.

例1設(shè)h=x0⊕x1⊕x5⊕x1x2⊕x3x4⊕x1x4⊕x1x2x3⊕x2x3x4⊕x1x2x3x4, 則

h的標(biāo)準(zhǔn)項(xiàng)表示為

2）生活習(xí)性。桃小食心蟲在渭北果區(qū)每年發(fā)生1～2代，以老熟幼蟲在土壤內(nèi)結(jié)繭越冬。一般5月下旬至6月上旬越冬幼蟲破繭出土，成蟲多產(chǎn)卵于果實(shí)梗（萼）洼處。幼蟲孵化后，蛀入果實(shí)，在果實(shí)內(nèi)蛀食20天左右，老熟后咬破果皮，脫果而出；脫果早的在土表作夏繭化蛹發(fā)生第2代，脫果晚的入土越冬。6月下旬至7月上中旬出現(xiàn)第1代成蟲，8月上中旬出現(xiàn)第2代幼蟲，在采果前大部分脫果。

命題4[13]設(shè)h ∈C?且其標(biāo)準(zhǔn)項(xiàng)表示為

l是線性布爾函數(shù), 則存在布爾函數(shù)g使得h=l ?g當(dāng)且僅當(dāng)

其中g(shù)cd 表示F2[x] 中多項(xiàng)式的最大公因式.

注1gcd(?(l1), ?(l2),··· ,?(ls))為h的最大階左線性星積因子.

下面給出求解最大階左線性星積因子的具體算法.

算法1 GetMaxOrderLeftLinearFactor Input: 特征函數(shù)h Output: 最大階左線性星積分解結(jié)果(l,g)1 將h 表示成標(biāo)準(zhǔn)項(xiàng)表示h = l1 ?t1 ⊕l2 ?t2 ⊕···⊕ls ?ts 2 L ←gcd(?(l1), ?(l2),··· ,?(ls))3 l ←??1(L)4 g ←??1(?(l1)/L)?t1 ⊕···⊕??1(?(ls)/L)?ts 5 Return (l,g)

3 主要結(jié)果

本節(jié)我們給出在h=g ?g情形下分解的主要結(jié)果. 由于線性情形是簡(jiǎn)單的, 所以僅考慮deg(g)≥2的情形, 并且我們令g ∈C?. 注意到g可以唯一地表示為以下形式

3.1 兩個(gè)必要條件

由命題2和星積運(yùn)算的定義知, 如下命題5顯然成立.

命題5設(shè)h=g ?g是特征函數(shù), 則ord(h) 為偶數(shù)且g是特征函數(shù)滿足ord(g)=ord(h)/2.

命題5表明, 當(dāng)ord(h) 為奇數(shù)時(shí), 不存在特征函數(shù)g, 使得h=g ?g.

下面進(jìn)一步討論h=g ?g的必要條件. 作為準(zhǔn)備, 先給出三個(gè)引理.引理1是偏導(dǎo)符號(hào)的一個(gè)性質(zhì),根據(jù)第2.1 節(jié)符號(hào)定義可知引理1是顯然成立的;引理2是f ?g與g的次數(shù)關(guān)系, 結(jié)論證明在文獻(xiàn)[20] 中已經(jīng)給出.

引理2[20]設(shè)f是布爾函數(shù)且f ?=0 或1,g是特征函數(shù), 則

進(jìn)一步, 上式等號(hào)成立當(dāng)且僅當(dāng)deg(f)=1.

基于上述兩個(gè)引理, 可以得到特征函數(shù)h的一個(gè)基本性質(zhì).

引理3若h=g ?g且h ∈C?,j1=minsub(h[>1]), 則j1=i1, 并且

證明:由式(3)可知

其中0j1. 在上述記號(hào)下, 有如下命題6.

命題6若h=g ?g, 且deg(h)≥2, 則z1≡z2≡···≡zk ≡0 mod 2,且g具有如下形式

其中deg(g′)≥2 且minsub(g′)>zk/2.

證明:由于h=g ?g=l1?l1⊕l1?g[>1]⊕g[>1]?g, 則

由引理3知j1=i1, 故

所以

且xzs/2∈T(l1), s=1,2,··· ,k, 即g具有如下形式

命題6不但給出了一個(gè)新的必要條件, 而且當(dāng)h=g ?g時(shí), 其還可以用于確定g的部分線性項(xiàng).

3.2 h =g ?g 的星積分解

本小節(jié)假定h=g ?g已知, 但g ∈C?未知, 針對(duì)兩種情形分別給出了兩個(gè)求取g的高效算法. 在第一類情形中, 基于對(duì)布爾函數(shù)求偏導(dǎo)降次的思想, 我們將g ?g的分解問題轉(zhuǎn)化為l ?g的分解問題, 其中l(wèi)是線性布爾函數(shù), 進(jìn)而利用現(xiàn)有的左線性星積分解算法求得g. 在第二類情形中, 我們首先構(gòu)建關(guān)于布爾函數(shù)求偏導(dǎo)的函數(shù)方程, 然后利用按照次數(shù)進(jìn)行“分層剝離” 的思想依次求取g[d], g[d?1], ··· , g[1], 從而最終求得g, 其中d=deg(g). 下面給出第一類情形的分解算法. 在引理3的基礎(chǔ)上, 定理1 將一類g的求解問題歸結(jié)為2.3 節(jié)中的左線性星積分解問題.

定理1若h=g ?g, 且g ∈C?滿足i1≥is ?is?1, s=2,3,··· ,t, 記

則有js=is, 進(jìn)一步有

證明:在式(4)定義下, 由引理3知,s=1 時(shí)結(jié)論成立; 假設(shè)s=k時(shí)結(jié)論也成立, 則當(dāng)s=k+1 時(shí)

分下面兩種情況討論:

(1) 當(dāng)lk+1=0 時(shí),jk+1=ik+1;

(2) 當(dāng)lk+1?= 0 時(shí),jk+1= min{ik+1,minsub{lk+1}+i1}, 由于i1≥ ik+1?ik且ik

因此由上述兩種情況得jk+1=ik+1. 于是,

綜上, 由歸納假設(shè)可知, 結(jié)論對(duì)s=1,2,··· ,t都成立.

對(duì)上述定理1, 當(dāng)s=t時(shí), 由式(4)定義可知,Qit,it?1,···,i1(g) 為線性函數(shù), 則由命題1-(5) 知

算法2 h=g ?g 型的第一類分解算法Input: 非奇異特征函數(shù)h Output: h = g ?g 對(duì)應(yīng)的因子g 1 h′ ←h 2 j1 ←minsub(h[>1])3 h ←Qj1 (h)4 j2 ←minsub(h[>1])5 s ←2 6 while j1 ≥js ?js?1 do 7h ←Qjs (h)8s++;9js ←minsub(h[>1])10 end 11 (l,g′) ←GetMaxOrderLeftLinearFactor(h)12 a ←?(l) 中因子x 的最大重?cái)?shù)13 L ←?(l)/xa 14 b ←ord(h)/2 ?ord(g′)?(a ?(js ?j1))15 ? ←{L1 : L1 |L and deg{L1} = b}16 if ? = ?then 17g ←xa?(js?j1) ?g′ ⊕x0 18Return g 19 end 20 for all L1 in ? do 21L2 ←xa?(js?j1) ·L1 22g ←??1(L2)?g′ ⊕x0 23if h′ = g ?g then 24Return g 25end 26 end

下面先對(duì)算法2 的時(shí)間復(fù)雜度進(jìn)行簡(jiǎn)要分析, 記N為h的項(xiàng)數(shù),D為h的次數(shù), 算法2 中第1 行到第10 行的時(shí)間復(fù)雜度上限為O(DN), 子函數(shù)GetMaxOrderLeftLinearFactor的時(shí)間復(fù)雜度上限為O(N), 第12 到20 行的時(shí)間復(fù)雜度相比之下可以忽略不計(jì), 則最終算法2 的時(shí)間復(fù)雜度為O(DN).

為了便于更準(zhǔn)確地理解算法2 的分解過程, 在本文附錄1 中我們給出了詳細(xì)分解示例.

當(dāng)定理1 條件不滿足時(shí), 情況有些復(fù)雜, 但依然可以通過類似定理1 的求偏導(dǎo)來求取g. 作為準(zhǔn)備, 我們首先給出引理4.

引理4若h=g ?g且g ∈C?滿足i1≥is ?is?1, s=2,3,··· ,k,i1+minsub(lk+1)

證明:在式(4)定義下, 由定理1 可知

這里s=2,3,··· ,t.

故s=k+1 結(jié)論成立. 綜上, 根據(jù)歸納假設(shè)可知引理結(jié)論成立.

當(dāng)引理5中s=t時(shí)有

根據(jù)式(4)定義可知deg(Qit,it?1,···,i1(g))=1, 下面給出定理2, 通過定理2 可唯一求解出特征函數(shù)g, 具體求解算法見算法3.

算法3 h=g ?g 型的第二類分解算法Input: 非奇異特征函數(shù)h Output: h = g ?g 對(duì)應(yīng)的因子g 1 h′ ←h 2 j1 ←minsub(h[>1])3 h ←Qj1 (h)4 j2 ←minsub(h[>1])5 s ←2 6 while j1 ≥js ?js?1 do 7h ←Qjs (h)8s++9js ←minsub(h[>1])10 end 11 h ←Qjs (h)12 if ord(h)?minsub(h) ≥ord(h′)/2 then 13Return None 14 end 15 d ←js ?j1 16 h ←σ?d(h)17 由h 得到i2,i3,··· ,it; Qi2,i1 (g), ··· ,Qit,it?1,···,i1 (g)18 h ←h ⊕Qj1 (h′)19 h ←Qit,it?1,···,i2 (h)20 由h 計(jì)算出g 21 Return g

定理2對(duì)于式(6), 記l0=Qit,it?1,···,i1(g), QH=Qit,it?1,···,i3,i2(H), d= deg(QH), 則d=deg(g) 且

即g是被QH唯一確定的.

證明:由星積運(yùn)算性質(zhì)以及偏導(dǎo)數(shù)定義可知deg(g) = deg(l0?g) =d; 且根據(jù)式(6)和定理中符號(hào)定義可知

下面按照次數(shù)分類, 得到下列等式

將上述等式移項(xiàng)整理則得到所證結(jié)論, 根據(jù)左線性星積分解的唯一性理論可知,g的各次項(xiàng)被QH唯一確定, 即g是被QH唯一確定的.

下面對(duì)算法3 的時(shí)間復(fù)雜度進(jìn)行簡(jiǎn)要分析, 記N為h的項(xiàng)數(shù),D為h的次數(shù), 算法3 中第1 行到第14 行的時(shí)間復(fù)雜度上限為O(DN), 第15 行到第19 行的時(shí)間復(fù)雜度上限為O(DN), 由h計(jì)算出g的時(shí)間復(fù)雜度上限為O(DN), 則算法3 的時(shí)間復(fù)雜度為O(DN).

為了便于更準(zhǔn)確地理解算法3 的分解過程, 在本文附錄2 中我們給出了詳細(xì)分解示例.

值得注意的是文獻(xiàn)[13] 中雖然給出了分解h=f ?g的一般算法, 但是在具體分解過程中需要合理猜測(cè)r[d?1],r[d?2],...,r[1](詳見文獻(xiàn)[13] 中的Section VI), 這使得分解算法的時(shí)間復(fù)雜度往往不可控制, 當(dāng)h的階數(shù)和項(xiàng)數(shù)稍大時(shí), 分解算法往往難以給出分解結(jié)果.

4 進(jìn)一步結(jié)果

本節(jié)在第3 節(jié)的基礎(chǔ)上, 進(jìn)一步給出相關(guān)結(jié)論, 主要分為三個(gè)小節(jié). 4.1 節(jié)是在第3 節(jié)的基礎(chǔ)上給出以非線性最大下標(biāo)求偏導(dǎo)的結(jié)果, 作為第3 節(jié)結(jié)論的補(bǔ)充, 可以處理第3 節(jié)無法處理的情形; 4.2 節(jié)給出一類一般情形的分解向h=g ?g分解的轉(zhuǎn)化, 從而可以快速實(shí)現(xiàn)分解; 4.3 節(jié)將h=g ?g的結(jié)論推廣到h=g ?g ?···?g這一情形.

4.1 以非線性最大下標(biāo)求偏導(dǎo)的結(jié)果

對(duì)任意的n階布爾函數(shù)f(x0,x1,··· ,xn), 記R(f(x0,x1,··· ,xn))=f(xn,xn?1,··· ,x0), 則由星積運(yùn)算的定義易知如下引理6成立.

引理6若h=f ?g, 則R(h)=R(f)?R(g).

由引理6知若h=g ?g, 則R(h)=R(g)?R(g). 因此對(duì)h非線性最大下標(biāo)求偏導(dǎo)等價(jià)于對(duì)R(h) 的非線性最小下標(biāo)求偏導(dǎo), 從而易得類似于第3 節(jié)的結(jié)論, 這里不再重復(fù)給出. 從分解角度看, 當(dāng)h不滿足第3 節(jié)的條件時(shí), 可以直接用R(h) 進(jìn)行判斷是否滿足條件, 不需要轉(zhuǎn)化為非線性最大下標(biāo)求偏導(dǎo).

4.2 h =f ?g 轉(zhuǎn)化為h =g ?g

已有的非線性星積分解算法的計(jì)算復(fù)雜度和存儲(chǔ)復(fù)雜度較高, 因此我們考慮一類特殊的非線性星積分解情形, 當(dāng)其星積因子較為“接近” 時(shí), 將這一類非線性星積分解轉(zhuǎn)化為便于分解的g ?g的情形, 從而降低這一類非線性星積分解的時(shí)間復(fù)雜度.

這里只考慮非平凡情形, 即h=f ?g, 其中deg(f)>1,deg(g)>1.

證明:已知

其中(f ⊕g)?g=(f ⊕g)[1]?g ⊕(f ⊕g)[>1]?g. 由f和g都是非奇異特征函數(shù)知

所以minsub((f ⊕g)[>1]?g)>i1, 因此

根據(jù)定理3 我們可以得到當(dāng)f和g較為“接近” 時(shí), 即其滿足條件minsub((f ⊕g)[>1])>i1時(shí),h=f ?g的分解就轉(zhuǎn)化為h=g ?g這一類型, 此時(shí)若g滿足第3 節(jié)的條件, 即可求解出g, 得到右星積因子, 通過文獻(xiàn)[13] 第VI-C 節(jié)結(jié)論可以求得左星積因子f.

4.3 h =g ?g ?···?g 的分解

上述部分主要研究h=g ?g的情形, 其分解方法可以推廣到一般的h=g ?g ?···?g這一情形, 從而可以得到h=g ?g ?···?g的兩類分解算法. 結(jié)論推廣主要利用歸納法以及引理1的結(jié)論, 將最左側(cè)的g看作h的左星積因子, 其余的看作h的右星積因子, 記作f, 則h=g ?f, 通過歸納和逐層求偏導(dǎo)即可得到推廣結(jié)論, 這里不再給出. 值得注意的是,g的個(gè)數(shù)的奇偶性影響類似式(5)中的右星積因子的形式, 當(dāng)其為偶數(shù)時(shí), 右星積因子為g ⊕x0, 當(dāng)其為奇數(shù)時(shí), 右星積因子為g, 該形式對(duì)第一類算法有影響, 但最終都可以利用左線性星積分解方法求得g.

5 結(jié)束語

本文主要探討h=g ?g型特征函數(shù)的星積分解問題, 以期能為一般的星積分解問題提供借鑒和探索分解之法. 針對(duì)兩類情形, 我們給出了由h=g ?g求取g的高效算法. 在第一類情形中, 基于對(duì)布爾函數(shù)求偏導(dǎo)降次的思想, 我們將g ?g的星積分解問題轉(zhuǎn)化為l ?g的星積分解問題, 其中l(wèi)是線性布爾函數(shù),然后基于現(xiàn)有的l ?g分解算法高效地求得g; 在第二類情形中, 我們首先給出關(guān)于h求偏導(dǎo)的函數(shù)方程,然后利用按次數(shù)進(jìn)行“分層剝離” 的思想依次求取g[d],g[d?1],··· ,g[1], 從而最終求取g, 其中g(shù)[k]的求取也是轉(zhuǎn)化為l ?g[k]的星積分解來實(shí)現(xiàn). 此外, 本文從星積分解的角度給出了兩個(gè)特征函數(shù)較為“接近” 的一種刻畫, 并將較為“接近” 的特征函數(shù)的星積分解問題轉(zhuǎn)化為h=g ?g的星積分解問題. 遺憾的是, 仍然存在本文算法無法解決的情形, 因此關(guān)于h=g ?g的進(jìn)一步研究是我們下一步工作的重點(diǎn). 另外, 需要進(jìn)一步研究如何由h=g ?g的星積分解探索一般的非線性星積分解.

由于j1=1, 此時(shí)

由于j2=2, 滿足條件j1≥j2?j1, 此時(shí)

由于j3=4, 不滿足條件j1≥j3?j2, 對(duì)Q2,1(h) 進(jìn)行左線性星積分解得

此時(shí)? 為空集, 則

驗(yàn)證可知,h=g ?g, 分解成功.

附錄2第二類情形示例

已知待分解的非奇異特征函數(shù)

由于j1=1, 此時(shí)

由于j2=3, 不滿足條件j1≥j2?j1, 此時(shí)

即Q1(g)=x2⊕x4x5, 因此i2=4, 且

下面按次數(shù)對(duì)g進(jìn)行求解.

則Q4(Q1(h)⊕Q1(g))=x3⊕x5⊕x6x7⊕x6x9x10⊕x11=x5?g ⊕Q4(x2?g),故deg(g)=3, 且

解得

因此g=x0⊕x1x2⊕x1x4x5⊕x6.

驗(yàn)證可知,h=g ?g, 分解成功.