基于編織法的de Bruijn序列差異性研究*

王向宇,王中孝

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

1 引言

由于de Bruijn序列具有周期最大、元素分布均衡、線性復(fù)雜度較高等良好的偽隨機(jī)性質(zhì),因此在序列密碼的研究領(lǐng)域中占有重要位置,其中de Bruijn序列的構(gòu)造問(wèn)題一直是研究的熱點(diǎn)問(wèn)題之一.文獻(xiàn)[1]用組合數(shù)學(xué)的方法給出一個(gè)構(gòu)造n級(jí)de Bruijn序列的算法,即prefer one算法,從而證明了對(duì)任意正整數(shù)n,皆存在n級(jí)de Bruijn序列,但該算法僅能生成一條n級(jí)de Bruijn序列.文獻(xiàn)[2]用圖論的方法證明了全體不平移等價(jià)的n級(jí) de Bruijn序列的個(gè)數(shù)為22n?1?n,但其證明方法不是構(gòu)造性的.文獻(xiàn)[3]總結(jié)了de Bruijn序列的構(gòu)造方法、線性復(fù)雜度和重量分布等研究成果.到目前為止,構(gòu)造de Bruijn序列的方法大致上可分為兩類,一類是基于文獻(xiàn)[4]中并圈法來(lái)構(gòu)造de Bruijn序列,如文獻(xiàn)[5–8].另一類是如文獻(xiàn) [9–11]中體現(xiàn)的利用較低級(jí)數(shù) de Bruijn序列構(gòu)造高級(jí)數(shù) de Bruijn序列的遞歸思想,基于文獻(xiàn)[12]中的編織法思想,文獻(xiàn)[13]從一條n級(jí)de Bruijn序列出發(fā)，利用編織法得到兩條編織序列,基于該序列的特殊性質(zhì),在特定位置上添加4個(gè)比特即可構(gòu)造出四條2n級(jí)de Bruijn序列.該算法不僅使得de Bruijn序列級(jí)數(shù)成倍增長(zhǎng),還能由一條 de Bruijn序列出發(fā)構(gòu)造多條 de Bruijn序列.迭代使用該算法,可以實(shí)現(xiàn)de Bruijn序列構(gòu)造規(guī)模的指數(shù)級(jí)增張.然而,從密碼設(shè)計(jì)的角度來(lái)看,除考慮構(gòu)造所得de Bruijn序列的數(shù)量之外,還應(yīng)當(dāng)考慮構(gòu)造所得de Bruijn序列的差異性,這是因?yàn)橄嗨频膁e Bruijn序列往往具有較長(zhǎng)的相同序列段,因此在局部上可被視為同一序列,而這應(yīng)當(dāng)在實(shí)際應(yīng)用中盡量避免.基于以上考慮,本文主要討論由一條n級(jí)de Bruijn序列出發(fā)利用編織法構(gòu)造所得的四條2n級(jí)de Bruijn序列的差異性問(wèn)題.

本文內(nèi)容按如下結(jié)構(gòu)進(jìn)行安排:第2節(jié)給出相關(guān)定義和準(zhǔn)備知識(shí);第3節(jié)討論由編織法所得四條2n級(jí)de Bruijn序列的差異性,由于其間的差異性由兩條編織序列的差異性唯一決定,而編織序列的差異性又可以轉(zhuǎn)化為兩個(gè)指定映射的差異性.映射的差異性問(wèn)題進(jìn)一步可歸結(jié)為對(duì)n長(zhǎng)狀態(tài)來(lái)源的研究,最終本文得到兩個(gè)映射出現(xiàn)差異的充要條件,進(jìn)而得到這兩個(gè)映射的差異數(shù)和差異率;第4節(jié)對(duì)本文進(jìn)行了總結(jié)并指出后續(xù)工作.

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

本文所討論序列皆為2元序列,設(shè)n是一個(gè)正整數(shù),用F2表示二元域,用表示F2上的n維向量空間,文中模運(yùn)算皆取最小非負(fù)剩余.

2.1 周期序列及狀態(tài)的位置

定義 1[14]對(duì)于序列=(a0a1a2···),如果存在一個(gè)正整數(shù)l滿足

al+k=ak,k=0,1,2,···

則稱是一個(gè)周期序列.滿足上式的全體l中的最小正整數(shù)稱為的周期.此外若無(wú)特別說(shuō)明,本文所討論的周期序列用該序列的第一個(gè)周期表示.

定義2對(duì)于任意一條周期為T的序列,將其重復(fù)m次可以得到一條新的序列,對(duì)序列的這一操作稱為m次復(fù)寫,并將m次復(fù)寫的結(jié)果記作.復(fù)寫序列用該序列的前mT個(gè)比特表示.

定義3對(duì)于周期序列=(b0b1···bT?1),稱bi為序列的第i位,i=0,1,···,T?1,若r長(zhǎng)狀態(tài)(s0s1···sr?1) 滿足

bi+jmodT=sj,j=0,1,···,r?1

則稱該狀態(tài)是周期序列b位于第i位的r長(zhǎng)狀態(tài),即考慮位置的r長(zhǎng)狀態(tài)可由該狀態(tài)第一比特所處的位置和狀態(tài)長(zhǎng)度r確定.

例1序列=(00010111)周期為8,其中(000)的第一比特0是序列的第0位,且該狀態(tài)是序列位于第0位的3長(zhǎng)狀態(tài),(1000)是序列位于第7位的4長(zhǎng)狀態(tài),(00)是序列位于第0位和第1位的2長(zhǎng)狀態(tài).

定義 4對(duì)于復(fù)寫序列=(b0b1···bT?1bT···bmT?1),稱bi為序列的第i位,記為,并且當(dāng)i≡jmodT時(shí),有

其中,i=0,1,···,mT?1,j=0,1,···,T?1.

若r長(zhǎng)狀態(tài) (s0s1···sr?1)滿足

其中,i=0,1,···,T?1,j=0,1,···,r?1.則稱該狀態(tài)是序列位于第i位的r長(zhǎng)狀態(tài).根據(jù)定義,給定一個(gè)r長(zhǎng)狀態(tài),它在序列的位置與其在序列中的位置相同.

例2序列=(00010111)周期為 8,則=(000101110001011100010111),其中為序列的第22位,此時(shí)=1.(1000)是序列位于第7位的4長(zhǎng)狀態(tài),(00)是序列位于第0位和第1位的2長(zhǎng)狀態(tài).

定義5給定周期序列c=(c0c1···cT?1),r長(zhǎng)狀態(tài) (ci+1ci+2···ci+r) 稱為r長(zhǎng)狀態(tài) (cici+1···ci+r?1)的后繼,更進(jìn)一步考慮n長(zhǎng)狀態(tài)及其位置,將位于第i位的n長(zhǎng)狀態(tài)記為ci=(cici+1···ci+n?1),即=(ci+1ci+2···ci+n) 是=(cici+1···ci+n?1) 的后繼,i=0,1,···,T?1. 記不考慮位置時(shí)的n長(zhǎng)狀態(tài).(這里所有下標(biāo)取模T的最小非負(fù)整數(shù))

定義7將周期序列循環(huán)右移一位的變換稱為的循環(huán)右移變換,記為R.設(shè)=(a0a1···aT?1),則在循環(huán)右移變換R下的像為:

定義Ri為循環(huán)右移變換R的i次復(fù)合,即

特別地,R0=.

定義8對(duì)于兩條周期序列和,若存在d∈N,使得=Rd,稱和平移等價(jià),記作;若不存在這樣的d,則稱和不平移等價(jià),記作?

2.2 de Bruijn序列及其變形

若一條序列的周期為2n,且2n個(gè)不同的n長(zhǎng)狀態(tài)在一個(gè)周期中出現(xiàn)且僅出現(xiàn)一次,則稱該序列為n級(jí)de Bruijn序列.對(duì)于一條n級(jí)de Bruijn序列,“減變形”和“加變形”規(guī)定如下:

“減變形”:將de Bruijn序列中n長(zhǎng)全0狀態(tài)替換為n?1長(zhǎng)全0狀態(tài),n長(zhǎng)全1狀態(tài)替換為n?1長(zhǎng)全1狀態(tài),得到一條周期為2n?2的新序列,記為序列.

“加變形”:將de Bruijn序列中n長(zhǎng)全0狀態(tài)替換為n+1長(zhǎng)全0狀態(tài),n長(zhǎng)全1狀態(tài)替換為n+1長(zhǎng)全1狀態(tài),得到一條周期為2n+2的新序列,記為序列.

2.3 編織法及其性質(zhì)

2.4 編織法構(gòu)造de Bruijn序列

綜上,利用編織法可實(shí)現(xiàn)由一條n級(jí)de Bruijn序列來(lái)構(gòu)造四條 2n級(jí)de Bruijn序列.進(jìn)一步地,迭代使用上述算法,即可實(shí)現(xiàn)由一條n級(jí)de Bruijn序列來(lái)快速構(gòu)造四的方冪條更大級(jí)數(shù)的de Bruijn序列.

3 主要結(jié)果

由定義9知,編織序列和分別決定了映射f和g,因此其間的差異性可以由映射f和g的差異性來(lái)刻畫(huà),而映射f和g的差異性定義如下.

定義 10對(duì)于映射f和g,若存在x∈A,使得

f(x)=g(x)

則稱映射f和g在x上無(wú)差異;若存在x∈A,使得

則稱映射f和g在x上有差異.進(jìn)一步地,令

引理 3設(shè)x=(e0e1···e2n?1)∈A,若 (e0e2···e2n?2)∈P{(1000···00),(0111···11)},則

滿足引理3條件的x有2n(2n?4)=22n?2n+2個(gè),即至少有22n?2n+2個(gè)x使得f(x)=g(x).引理3中給出的條件是f(x)=g(x)成立的充分不必要條件,有引理4和引理5為證.

引理 4設(shè)x=(e0e1···e2n?1)∈A, 若 (e0e2···e2n?2)=(1000···00) 并且 (e1e3···e2n?1)=(0000···00)或 (1111···11),也即當(dāng)x=(1000···00) 或x=(1101···01) 時(shí),有

f(x)=g(x)

證明:當(dāng)x= (1000···00) 時(shí), 即 (e0e2···e2n?2)= (1000···00) 且 (e1e3···e2n?1)=(0000···00), 由于 (0000···00) 只能來(lái)源于序列, 因此 (1000···00) 來(lái)源于序列, 此時(shí)

f(x)=g(x)=e2n=1

當(dāng)x=(1101···01) 時(shí),即 (e0e2···e2n?2)=(1000···00) 且 (e1e3···e2n?1)=(1111···11),由于(1111···11)只能來(lái)源于序列,因此 (1000···00) 來(lái)源于序列,此時(shí)

f(x)=g(x)=e2n=1

綜上,當(dāng)x=(1000···00) 或x=(1101···01) 時(shí),有f(x)=g(x).

同理可證明以下引理.

引理 5設(shè)x=(e0e1···e2n?1)∈A, 若 (e0e2···e2n?2)=(0111···11), 并且 (e1e3···e2n?1)=(0000···00)或 (1111···11),也即當(dāng)x=(0010···10) 或x=(0111···11) 時(shí),有

f(x)=g(x)

由引理3–5可知, 當(dāng)x∈{(0010···10),(0111···11),(1000···00),(1101···01)}或 (e0e2···e2n?2)∈P{(1000···0),(0111···11)}時(shí),有f(x)=g(x).此時(shí),共有 22n?2n+2+4個(gè)x使得f(x)=g(x).以下討論映射f和g出現(xiàn)差異的情況.

引理 6設(shè)x=(e0e1···e2n?1)∈A,若 (e0e2···e2n?2)=(1000···00) 且 (e1e3···e2n?1)∈P,則

綜上可得,當(dāng) (e0e2···e2n?2)=(1000···00) 時(shí),

f(x)=1,g(x)=0

若 (e1e3···e2n?1)∈,有

f(x)=0,g(x)=1

綜上可知,(e1e3···e2n?1)遍歷了序列中所有的n長(zhǎng)狀態(tài),也即集合P中所有元素,故當(dāng)(e0e2···e2n?2)=(1000···00) 且 (e1e3···e2n?1)∈P,有f(x)(x).

由引理6可知,滿足引理6條件的x有2n?2個(gè),即有2n?2個(gè)x使得f(x)(x),同理可證如下引理.

引理 7設(shè)x=(e0e1···e2n?1)∈A,若 (e0e2···e2n?2)=(0111···11) 且 (e1e3···e2n?1)∈P,則

此時(shí)有2n?2個(gè)x使得f(x)(x).最后考慮僅在序列中出現(xiàn)的n長(zhǎng)狀態(tài) (0000···00)和 (1111···11).

引理 8設(shè)x=(e0e1···e2n?1)∈A,若 (e0e2···e2n?2)=(0000···00),則

(2) 當(dāng) (0000···00) 為時(shí),=(0000···00) 的后繼為=(0000···01),同上討論可得,

綜上可得,當(dāng) (e0e2···e2n?2)=(0000···00) 時(shí),

因此, 對(duì)于x=(e0e1···e2n?1)∈A, 當(dāng) (e0e2···e2n?2)=(0000···00) 時(shí), 若 (e1e3···e2n?1)∈,有

f(x)=0,g(x)=1

f(x)=1,g(x)=0

綜上可得,當(dāng) (e0e2···e2n?2)=(0000···00),有f(x)(x).

由引理8可知,滿足引理8條件的x有2n?2個(gè),即有2n?2個(gè)x使得f(x)(x).同理可知,當(dāng)(e0e2···e2n?2)=(1111···11) 時(shí),可得引理9.

引理 9設(shè)x=(e0e1···e2n?1)∈A,若 (e0e2···e2n?2)=(1111···11),則

此時(shí)有 2n?2個(gè)x使得f(x)?=g(x).由引理6–9可知,共有 4(2n?2)=2n+2?8個(gè)x使得f(x)?=g(x).再由引理3–5可知,有 22n?2n+2+4個(gè)x使得f(x)=g(x),而|A|=22n?4,映射f和g在 22n?2n+2+4個(gè)元素上無(wú)差異,在 2n+2?8個(gè)元素上有差異,由計(jì)數(shù)可知,引理3–5和引理6–9事實(shí)上給出了映射f和g出現(xiàn)差異的充要條件,整理得到定理1.

定理 1對(duì)于定義9中映射f和g,設(shè)x=(e0e1···e2n?1)∈A,f(x)(x)當(dāng)且僅當(dāng)滿足下列情形之一:

(1)(e0e2···e2n?2)=(1000···00) 且 (e1e3···e2n?1)∈P;

(2)(e0e2···e2n?2)=(0111···11) 且 (e1e3···e2n?1)∈P;

(3)(e0e2···e2n?2)=(0000···00) 或 (1111···11).

表1 編織序列和的差異Table 1 Differences betweenand

表1 編織序列和的差異Table 1 Differences betweenand

注 1表中√ 表示有差異,×表示無(wú)差異

4長(zhǎng)狀態(tài) I 1=In(b,a3) I 2=In(a3,b)有無(wú)差異(0001) 0 1 √(0010) 0 0 ×(0011) 1 0 √(0100) 1 0 √(0110) 0 1 √(0111) 0 0 ×(1000) 1 1 ×(1001) 1 0 √(1011) 0 1 √(1100) 0 1 √(1101) 1 1 ×(1110) 1 0 √

4 結(jié)束語(yǔ)

雖然利用編織法可以實(shí)現(xiàn)由較低級(jí)數(shù)de Bruijn序列構(gòu)造高級(jí)數(shù)de Bruijn序列,但是需要考慮兩個(gè)方面的問(wèn)題.

一方面,由一條n級(jí)de Bruijn序列編織構(gòu)造的兩條編織序列,其差異率為

表2 n=2至6對(duì)應(yīng)的差異率Table 2 Difference rates for some n

由表2可知,當(dāng)n逐漸增大時(shí),由編織法生成的兩條編織序列的差異數(shù)雖然逐漸增長(zhǎng),但是差異數(shù)的增長(zhǎng)速度遠(yuǎn)低于編織序列2n長(zhǎng)狀態(tài)個(gè)數(shù)的增長(zhǎng)速度,導(dǎo)致差異率越來(lái)越低.當(dāng)n→∞時(shí),事實(shí)上,當(dāng)n=12時(shí),差異率為0.0009761,已經(jīng)不足千分之一,也即通過(guò)編織法得到的兩條編織序列的相似性超過(guò)了99.9%.因此,雖然利用編織法可構(gòu)造出更高級(jí)數(shù)的de Bruijn序列,但這些de Bruijn序列相似性較高,這也表明從一條n級(jí)de Bruijn序列出發(fā)利用編織法構(gòu)造的2n級(jí)de Bruijn序列,級(jí)數(shù)n與所得編織序列的差異率是一對(duì)矛盾,差異率隨著級(jí)數(shù)n的增大而減少.

另一方面,注意到,多次利用編織法可從一條n級(jí) de Bruijn序列出發(fā)快速地構(gòu)造大量的更高級(jí)數(shù) de Bruijn序列.例如,當(dāng)n=2時(shí),一次編織可以得到兩條差異率為 0.667的編織序列,補(bǔ)足所缺片段得到四條 4級(jí) de Bruijn序列,再以這些 4級(jí) de Bruijn序列為基礎(chǔ)序列,進(jìn)一步編織并補(bǔ)足所缺片段可得到十六條 8級(jí) de Bruijn序列,也即從一條 2級(jí) de Bruijn序列出發(fā),利用編織法兩次可得到十六條 8級(jí) de Bruijn序列,依次下去,可得到四的方冪條 de Bruijn序列,具體過(guò)程參見(jiàn)文獻(xiàn) [13].從一條n級(jí) de Bruijn序列出發(fā),經(jīng)過(guò)一次編織所得到的編織序列的差異性 (組內(nèi)差異),本文已研究清楚.在編織序列基礎(chǔ)上補(bǔ)足所缺片段得到四條 2n級(jí) de Bruijn序列,以差異性較大的兩條2n級(jí)de Bruijn序列為基礎(chǔ)序列,它們經(jīng)過(guò)編織所得序列的差異性(組間差異),是下一步需要考慮的問(wèn)題.