田金兵，邢 福弟，劉 古勝

（1.海南師范大學(xué) 初 等教育學(xué)院，海南 海 口 5 71158；2.荊楚理工學(xué)院 數(shù) 理學(xué)院，湖北 荊 門448200）

一類大集合容量偽隨機(jī)序列集的線性復(fù)雜度研究

田金兵1，邢 福弟1，劉 古勝2

（1.海南師范大學(xué) 初 等教育學(xué)院，海南 海 口 5 71158；2.荊楚理工學(xué)院 數(shù) 理學(xué)院，湖北 荊 門448200）

具有大線性復(fù)雜度的序列可以抵抗Berlekamp-Massey算法攻擊，提高數(shù)據(jù)的安全性，設(shè)計(jì)大線性復(fù)雜度偽隨機(jī)序列是一個重要課題.使用d-齊次函數(shù)是增大序列的線性復(fù)雜度的一個有效方法.本文對正整數(shù)n=3m提出了一類周期為3n-1集合容量為3n的新序列集S（r），這里（r，3m-1）=1且1≤r＜3m-1.通過取適當(dāng)?shù)膮?shù)r，精確地計(jì)算出了它的線性復(fù)雜度.

序列；集合容量；線性復(fù)雜度

在密碼學(xué)中，周期序列的線性復(fù)雜度指的是產(chǎn)生偽隨機(jī)序列的最短線性反饋移位寄存器的長度，是衡量流密碼系統(tǒng)強(qiáng)度的一項(xiàng)重要指標(biāo).在某些應(yīng)用環(huán)境中的偽隨機(jī)序列應(yīng)具有較大的線性復(fù)雜度，這是因?yàn)榫€性復(fù)雜度小的序列是不安全的，密碼分析者在知道這個序列少量元素的情況下可以用Berlekamp-Massey算法破譯整個序列.因此，設(shè)計(jì)出具有較大線性復(fù)雜度偽隨機(jī)序列一直是序列研究中的一個重要課題.

在文獻(xiàn)[1]中，Klapper給出了一種增大d-齊次序列的線性復(fù)雜度的方法，人們證明了幾類有較大的線性復(fù)雜度下界的d-齊次序列，如對小集合Kasami序列的各種推廣［1-3］，這些序列有較大的線性復(fù)雜度，但它們的集合容量相對于序列長度依然較小.本文對于正整數(shù)n=3m給出了一類大集合容量的周期序列集 S（r），這里（r，3m-1） =1且 1 ≤r＜3m-1.通過取，精確計(jì)算出了它的線性復(fù)雜度為m·6w.證明了這類序列集有較大的線性復(fù)雜度.

1 基礎(chǔ)知識

跡函數(shù)具有下列基本性質(zhì)：

2 新序列集的構(gòu)造

顯然，如上所定義的序列集周期為3n，集合容量為3n-1，下面來研究它的線性復(fù)雜度.

Key在文獻(xiàn)[4]中給出了計(jì)算序列的線性復(fù)雜度的方法：如果令 x = αt，此時二元序列 s（r）（t）可寫成一個關(guān)于變量 s（r）（t）的多項(xiàng)式，那么二元序列s（r）（t）的線性復(fù)雜度 L S（s（r）（t））等于把 s（r）（t）展成關(guān)于變量x的多項(xiàng)式中次數(shù)不同的非零單項(xiàng)式的個數(shù).Antweiler M.和B?mer L.把這個結(jié)論推廣到p元序列中［5］.

引理 1 當(dāng) j≠j′時，Kj（x）和Kj′（x）關(guān)于變量的展開式中非零單項(xiàng)式的次數(shù)互不相同.

證明 由于y=y3m-1，因此只需證明對于j≠j′總有 3jr≡3j′r（mod3m-1）.事實(shí)上，如果3jr ≡ 3j′r（mod3m-1），注意到 gcd（r，3m-1） =1，那么 3jr≡3j′r（mod3m-1），從而有 i=i′.

顯然對于不同的j，Kj（x）關(guān)于變量x的展開式中非零單項(xiàng)式的個數(shù)相同.由引理1知，序列S（r）的線性復(fù)雜度 LS（S（r））等于 Kj（x）展開式中非零單項(xiàng)式的個數(shù)的m倍.令，則 Kj（x）展開式中非零單項(xiàng)式的個數(shù)和Φ（y）展開式中非零單項(xiàng)式的個數(shù)相同.這樣就將計(jì)算序列S（r）的線性復(fù)雜度問題轉(zhuǎn)化成計(jì)算Φ（y）展開式中非零單項(xiàng)式的個數(shù)問題.

為了敘述的方便，定義集合的加法及數(shù)乘：

A⊕B={a+b|a∈A，b∈B}，μA={μA|a∈A}，μ為常數(shù).

同時記 c·3m+d= （c，d），定義其加法及數(shù)乘：

并規(guī)定（ci，di） = （cj，dj）當(dāng)且僅當(dāng) ci=cj，di=dj.

顯然Φ（y）展開式中關(guān)于y的指數(shù)構(gòu)成的集合為

那么Φ（y）中關(guān)于的最大指數(shù)小于33m-1，因此Φ（y）展開式中關(guān)于y的非零單項(xiàng)式的個數(shù)就等于集合E種元素的個數(shù).

引理2 集合E共有6w個元素.

由上面的討論立即得到：

3 結(jié)論

從上面的分析可知，本文給出的序列集不僅具有大的集合容量，而且具有較大的線性復(fù)雜度，特別地，當(dāng)γi=1時，No證明了它是一條具有理想自相關(guān)的序列.這類序列適用于對線性復(fù)雜度要求較高的應(yīng)用環(huán)境中.

表1 序列集S（r）與其它序列集的比較Fig.1 Comparison of the sequence S（r）with other sequences

［1］Klapper A M.D-form sequences:families of sequences with low correlation valuesand large linear spans[J].IEEE TransInform Theory,1995,41(2):423-431.

［2］No J S,Kumar P V.A new family of binary pseudorandom sequenceshaving optimal periodic correlation propertiesand large linear span[J].IEEE TransInform Theory,1989,35(2):371-379.

［3］Zeng X Y,HU L,LIU Q C.A family of binary sequences with optimal correlation property and large linear span[C].Proceedings of the 2006 IEEE International Conference on Communications.Istanbul,Turkey,2006.

［4］Key E L.An analysis of the structure and complexity of nonlinear binary sequence generators[J].IEEE Trans Inform Theory,1976,22(6):732-736.

［5］Antweiler M L.Complex sequences over with two-level autocorrelation function and a large linear span[J].IEEE TransInform Theory,1992,38(1):120-130.

［6］Jang JW,Kim Y S,No JS,et al.New family of p-ary sequences with ideal autocorrelation and large linear span[J].IEEE TransInform Theory,2004,50:1839-1844.

［7］Kumar P V,Moreno O.Prime-phase sequenceswith periodic correcation propertiesbetter than binary sequences[J].IEEE TransInform Theory,1991,37:603-616.

［8］Liu S C,Komo J F.Nonbinary Kasami sequences over GF(p)[J].IEEE TransInform Theory,1992,38:1409-1412.

責(zé)任編輯：畢和平

Study on Linear Span of a Pseudorandom Sequences Family with Large Family Size

TIAN Jinbing1， XING Fudi1， LIU Gusheng2
（1.College of Elementary Education，Hainan Normal University，Haikou 571158，China；2.School of Mathematics and Physics，Jingchu University of Technology，Jingmen 448200，China）

Application of sequences with large linear span can efficiently resist Berlekamp-Massey attack and improve security of data.The design of sequences with large linear span was an important research problem.A useful approach to construct sequences with large linear span was based on d-form function.For a positive integer n=3m,a sequences family S（r）with optimal correlation was proposed，where （r，3m-1） =1 and 1 ≤ r ＜ 3m-1.By taking suitable values of the parameter r,its linear span by in this paper was calculated accurately.

sequences；family size;linear span

TN 918.1

A

1674-4942（2010）03-0256-03

2010-04-30

海南師范大學(xué)青年教師資助項(xiàng)目（QN0802）；海南省自然科學(xué)基金資助項(xiàng)目（808152）