王向宇,王中孝

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

1 引言

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

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

2 準(zhǔn)備知識

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

特別地,R0=.

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

2.2 de Bruijn序列及其變形

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

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

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

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

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

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

3 主要結(jié)果

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

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

f(x)=g(x)

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

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

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

滿足引理3條件的x有2n(2n?4)=22n?2n+2個,即至少有22n?2n+2個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) 時,有

f(x)=g(x)

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

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

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

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

綜上,當(dāng)x=(1000···00) 或x=(1101···01) 時,有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) 時,有

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)}時,有f(x)=g(x).此時,共有 22n?2n+2+4個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) 時,

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

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

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

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

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

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

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

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

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

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

因此, 對于x=(e0e1···e2n?1)∈A, 當(dāng) (e0e2···e2n?2)=(0000···00) 時, 若 (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個,即有2n?2個x使得f(x)(x).同理可知,當(dāng)(e0e2···e2n?2)=(1111···11) 時,可得引理9.

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

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

定理 1對于定義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表中√ 表示有差異,×表示無差異

4長狀態(tài) I 1=In(b,a3) I 2=In(a3,b)有無差異(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é)束語

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

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

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

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

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