一類大集合容量偽隨機序列集的線性復雜度研究

田金兵，邢 福弟，劉 古勝

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

一類大集合容量偽隨機序列集的線性復雜度研究

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

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

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

序列；集合容量；線性復雜度

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

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

1 基礎知識

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

2 新序列集的構造

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

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

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

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

顯然對于不同的j，Kj（x）關于變量x的展開式中非零單項式的個數(shù)相同.由引理1知，序列S（r）的線性復雜度 LS（S（r））等于 Kj（x）展開式中非零單項式的個數(shù)的m倍.令，則 Kj（x）展開式中非零單項式的個數(shù)和Φ（y）展開式中非零單項式的個數(shù)相同.這樣就將計算序列S（r）的線性復雜度問題轉化成計算Φ（y）展開式中非零單項式的個數(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）當且僅當 ci=cj，di=dj.

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

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

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

由上面的討論立即得到：

3 結論

從上面的分析可知，本文給出的序列集不僅具有大的集合容量，而且具有較大的線性復雜度，特別地，當γi=1時，No證明了它是一條具有理想自相關的序列.這類序列適用于對線性復雜度要求較高的應用環(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.

責任編輯：畢和平

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

海南師范大學青年教師資助項目（QN0802）；海南省自然科學基金資助項目（808152）