關于二元割圓序列的k-錯線性復雜度

陳智雄，吳晨煌,2

（1. 莆田學院福建省高校應用數學重點實驗室，福建 莆田 351100；2. 電子科技大學計算機科學與工程學院，四川 成都 611731）

1 引言

設有限域 Fp={0,1,… ,p-1}，其中p為奇素數。g為模p的一個本原根。若r|（p- 1）, 則r階割圓類定義為

其中,j=0 ,1,… ,r-1 。易知，構成 Fp{0}的一個劃分，并被廣泛應用于定義偽隨機序列[1]。

當r=2時，Legendre序列（su）[2-4]定義為

其中，u≥0。

當r=4時, Ding-Helleseth-Lam序列定義為

其中，u≥0。

當r=6且p形如24x+27，x∈?時，Hall六次剩余序列（su）[6-7]定義為

其中，u≥0。

需要注意的是，在文獻[6-7]中，g的選擇需滿足

上述幾類二元序列已受到廣泛的關注和研究。研究表明，這些二元序列具有好的偽隨機特性，包括一致分布性、最優相關性、高的線性復雜度等[1-3,5,6,8-12]。Xiong等[13]證明了 Legendre、Ding-Helleseth-Lam二元序列的2-adic復雜度等于周期p。最近，Su等[14]基于Ding-Helleseth-Lam二元序列使用交織的方法構造了一個周期為4p的具有優的自相關值的二元序列。通常把上面這種Z*（p為素數）上的割圓類稱為經典割圓類，對應的序列稱為經典割圓序列，而把Zn*（n為合數）上的割圓類稱為廣義割圓類，對應的序列稱為廣義割圓序列[15-22]。

文獻[23-24]把上述類型序列（su）視為p-進制序列并研究了其在有限域Fp上的k-錯線性復雜度。但是，（su）在F2上的k-錯線性復雜度還未徹底解決。文獻[1, 25]證明了任意的非常數二元序列的k-錯線性復雜度的一個下界。

命題 1（[1，Theorem 3.3.1]）對周期為p的任意非常數二元序列（su），其在F2上的k-錯線性復雜度 LCk（（su）） 滿 足k＜min{WH（（su））,p-WH（（su））}時，LCk（（su））≥o rdp（2） 。其中，ordp（2） 表示2在模p的階，WH（（su）） 表示序列（su） 的一個周期中所含1的個數。

本文工作主要是考慮由經典割圓類定義的序列（su）的k-錯線性復雜度。本文計算了 Legendre序列、Ding-Helleseth-Lam序列和Hall六次剩余序列在F2上的1-錯線性復雜度，并限制2在模p的階的某些取值，給出了這些序列在F2上的k-錯線性復雜度的一些結果。周期序列的離散傅里葉變換在本文的證明中起到了關鍵作用。

下面介紹線性復雜度、k-錯線性復雜度和周期序列的離散傅里葉變換等概念。

對于F2上周期為T的序列（su），其線性復雜度（記為LC（（su）））定義為（su） 滿足F2上的如下線性遞歸關系的最小階L。

那么，（su）在F2上的線性復雜度可通過式（4）計算。

對于整數k≥0，（su）在F2上的k-錯線性復雜度（記為LCk（（su）））是指在序列的一個周期中改變至多k個元素后所得這些序列在F2上的線性復雜度的最小值[26]。即

其中，（eu） 為周期為T的錯誤序列，WH（（eu）） 為（eu）的一個周期中所含1的個數。k-錯線性復雜度也被稱為球體復雜度[27]，本文不做詳細描述。易知，LC0（（su））= L C（（su）） ，且

其中，l=WH（（su）） 。

線性復雜度和k-錯線性復雜度是序列的重要密碼學性質，它們刻畫的是序列的可預測性，從而衡量該序列是否適用于密碼學領域。從密碼學應用角度考慮，一個序列的線性復雜度應盡可能大，并且序列在改變若干項后其線性復雜度不應明顯降低。

對于奇數T，序列（su）的離散傅里葉變換（ρ0, ρ1, … ,ρT-1） 和序列（su） 的線性復雜度具有緊密的聯系。記m=o rdT（2）表示2在模T的乘法階。對于T階本原單位根 β ∈F2m，離散傅里葉變換（DFT，discrete Fourier transform）[28-29]定義為

Blahut定理[30]給出了序列（su）的線性復雜度及其與DFT之間的關系，如式（7）所示。

其中，#{?}表示集合{?}中的元素個數。

對于給定的β，G（X）在模xT-1下是唯一確定的，G（X）也稱為序列（su）對應于β的defining多項式[34]。

2 離散傅里葉變換

Alecu 和 Sǎlǎgean[33-34]利用離散傅里葉變換給出了一個計算序列的k-錯線性復雜度的近似算法。他們的方法有助于本文考慮 Legendre序列、Ding-Helleseth-Lam 序列和Hall六次剩余序列的k-錯線性復雜度。本節計算了這些序列的離散傅里葉變換。更詳細的討論見文獻[32]。

其中，u∈Dj。下文中D（r）下標的計算都是在模r下進行的，即對所有的0≤l＜r，有定義

其中，0≤l＜r。本文首先給出并證明如下關于內積計算的引理，其中0≤i,j＜r。

引理1設β為F2的某一個擴域上的p階本原單位根。對任意一對整數i,j滿足0≤i,j＜r，有

證明 對任意的0≤l＜r，由于可得

設ord（γw）表示γw的階。由于β是p階本原單位根，則有ord（γw） |p。若ord（γw）=p，則

若ord（γw）=1，則

下面分別計算使ord（γw）=1和ord（γw）=p的元素的個數。

可以注意到ord（γw）=1當且僅當由于則也就 是說 ， 存 在使等式成立，當且僅當i-j） 并且w是唯一的，因此，當時，有個元素滿足ord（γw）=p，而只有一個滿足ord（γw）=1。 若則對所有的

綜上所述，可得

證畢。

下面給出Legendre序列、Ding-Helleseth-Lam序列和Hall六次剩余序列的Mattson-Solomon 多項式。

命題2設β為F2的某一個擴域上的p階本原單位根滿足：當當那么，式（1）定義的Legendre序列（su）的對應于β的Mattson-Solomon 多項式為

需要說明的是，當p≡ ± 1（m o d8）時，選擇這樣雖然得到不同形式的G（x），但是并不影響本文的討論結果。

證明由引理 1可得式（1）定義的 Legendre序列（su）的Mattson-Solomon多項式為

顯然，在已知條件D0（2）（β） 的取值假設下，當p≡ 1（m o d 4）時，易知

即su=G（βu），當u≥0。對于p≡ 3（mod 4）的情況可類似驗證。

證畢。

由式（7）可得如下結論。

推論1[3]由式（1）定義的Legendre序列（su）的線性復雜度為

對于r=4的情況，由4|（p-1），則p滿足p≡ 1（mod 8）或p≡-3（m o d 8）。由引理 1可知，由式（2）定義的 Ding-Helleseth-Lam 序列（su） 的Mattson-Solomon多項式如下所示。

當p≡ 1（mod 8）時，

當p≡-3（mod 8）時，

和

因此，可得

其中，0≤i≤4。

注意到，若p≡ 1（mod 8），則（即2 是模p的平方剩余），有綜上所述，可得命題3。

命題3設β為F2的某一個擴域上的p階本原單位根。

1）若p≡ 1（mod8），令則由式（2）定義的Ding-Helleseth-Lam序列（su） 對應于β的Mattson-Solomon多項式G（x）如下。

2）若p≡ -3（m o d 8）, 令θ∈F16且 θ4=1+θ ，則 由 式（2）定 義 的Ding-Helleseth-Lam 序列（su） 對應于β的Mattson-Solomon 多項式G（x）如下。

若2∈D（4），則

若2∈D（4），則

在命題 3 中，當p≡ 1（mod 8）時，若選擇的其他取值，雖然得到不同形式的G（x），但是并不影響討論結果。

推論 2[5]由式（2）定義的 Ding-Helleseth-Lam序列（su）的線性復雜度為

對于 Hall六次剩余序列，由于p=4x2+ 2 7，則有p≡-1（m o d 8）或p≡ 3（mod 8）。

此外，若p≡-1（m o d 8），那么由[6, Lemma 2]，可 知和中有一個值為1，其他2個值為0，其中β是F2的某一個擴域的p階本原單位根。由[6,Theorem 1]， 存 在 β 使 得對同一個β，由[6, Theorem 1]的證明可得式（9）。

若p≡ 3（mod 8） ，類似地，由[6, Lemma 1]，可 知和而其他2個值為其中i=0,1,2。注意到

則由引理1，可得命題4。

命題 4設β是F2的某個擴域上的p階本原單位根，且當p≡-1（mod8）時，β滿足式（9）；而當p≡ 3（mod 8） 時， β滿足式（10），則由式（3）定義的Hall六次剩余序列（su）對應于β的Mattson-Solomon多項式如下所示。

若p≡-1（m o d 8），則

若p≡ 3（mod8），則

推論 3[6]由式（3）定義的 Hall六次剩余序列（su） 的線性復雜度為

3 k-錯線性復雜度

由式（5）可知，周期為p的二元序列（su）的k-錯線性復雜度是指在改變序列（su）的第一個周期中至多k項后（隨后的其他周期中做相同改變），可得序列（）的最小線性復雜度，即

其中，（eu）為一個錯誤序列滿足WH（（eu）） ≤k。受到文獻[33-34]的啟發，下面給出使用（eu）的離散傅里葉變換求序列的k-錯線性復雜度的方法。

由此證明，序列（su）在改變若干項之后其線性復雜度降低了。

3.1 1-錯線性復雜度

命題 5由式（1）定義的 Legendre序列（su） 在F2上的1-錯線性復雜度如下

證明不妨設錯誤序列（eu）的第一個周期中對某個 0 ≤u0＜p滿足eu0=1 ，而對其他0≤u≠u0＜p滿足eu= 0 。（eu）的離散傅里葉變換為η=βiu0,0≤i＜p。特別地，若u=0，則對所有0的 0≤i＜p有 ηi=1；否則，η0=1且對所有的1≤i＜p有ηi的階為p。

下面考慮p≡-1（m o d 8）的情況。由命題 2和式（11），可得

若u0≠0，則對所有的1≤i＜p有 ξi≠0，且修改后的序列的線性復雜度滿足而當u0=0時，有

這說明若改變序列（su）的第一項s0的值后，其線性復雜度從這就證明了第一種情況，而對于其他3種情況的證明方法類似。

證畢。

用命題5的證明方法，可以得到下面2個結論。

命題 6由式（2）定義的 Ding-Helleseth-Lam 序列（su）在F2上的1-錯線性復雜度為

命題7由式（3）定義的Hall六次剩余序列（su）在F2上的1-錯線性復雜度為

3.2 k-錯線性復雜度: 幾個特殊情況

對于k≥2的情況，要確定 Legendre序列、Ding-Helleseth-Lam序列和Hall六次剩余序列的k-錯線性復雜度是不容易的。但是，在一些特定的條件下可以得到部分結果。通過錯誤序列（eu）的離散傅里葉變換（η0, η1, … ,ηp-1） 的適當取值，并通過式（11）使得式（13）成立。

也就是說，改變序列（su） 的WH（（eu）） 項可使其線性復雜度降低。然后，從（η0,η1,…,ηp-1） 中計算得到（eu） ，從而得到WH（（eu）） ，即k的值。

其中g為第1節中定義的模p的本原元。令

設?i表示集合Ti中的最小元素值（也稱為陪集首元），其中0≤i＜d。對于一個二元序列的離散傅里葉變換為并定 義的 DFT-leader-vector為

由上述T0的定義易知，DFT-leader-vector是由唯一確定的，反之亦然。具體地，若

當p≡-3（mod 8）時，

當p≡ 3（mod8）時，

命題8設，則由式（1）定義的Legendre序列在F2上的k-錯線性復雜度如下。

當p≡ 1（mod8）時，

當p≡-1（mod8）時，

證明由于2是模p的平方剩余，因此，p≡ 1（mod 8）或p≡-1（mod8）。那么，由推論1、命題1和命題5即得所要結果。

命題 9設則由式（1）定義的Legendre序列在F2上的k-錯線性復雜度如下

或

證明由另外，根據上述定義的Ti，有由命題2中假設的或

再由命題 2，序列（su）的離散傅里葉變換（ρ0,ρ1,… ,ρp-1） 的DFT-leader-vector是[0；1,0,1,0]。為了使（su）的k-錯線性復雜度降低，即使序列的離散傅里葉變換滿足

由式（11）可知，錯誤序列（eu）的離散傅里葉變換有以下幾種情況。

取序列（eu） 的離散傅里葉變換的 DFT-leader-vector 為[η0；1 ,1,1,0]，序列（su） 的線性復雜度從降低為則可通過如下計算得到（eu） 。

若命題2中選擇的β滿足T0（β）=T2（β）=1，則設η0=0 。由于則有或T1（β）=1且T3（β）= 0 。可得

由此完成了第一種情況的證明。

若命題2中選擇的β滿足T0（β）=T2（β）= 0 ，選擇η0=1，則可計算得到滿足的錯誤序列（eu），進而有由命題1可完成第二種情況的證明。

證畢。

下面考慮由式（2）定義的Ding-Helleseth-Lam序列（su） 。若ordp（2）=p-1 ，則有由推論2、命題1和命題3可得

命題10設由式（2）定義的Ding-Helleseth-Lam序列（su）在F2上的k-錯線性復雜度為

或

證明由命題3可知，（su）的離散傅里葉變換為

取（eu） 的離散傅里葉變換（η0, η1,… ,ηp-1） 為

其中，δ ∈F2。通過如下方式計算得到（eu） 。

若命題3中選擇的β滿足式（13），則選擇η0=1和再由命題1即可完成第二種情況的證明。證畢。

命題11設則由式（2）定義的Ding-Helleseth-Lam序列（su）在F2上的k-錯線性復雜度為

或

證明由于則有且其中0≤i＜4。容易驗證每個T（β）∈F且在命題 3的假設下，若則式（16）或式（17）成立。

再由命題3可知，（su）的DFT-leader-vector為[0；0,0,1,1]。仿照命題9的證明，通過式（16）選擇錯誤 序 列（eu） 的離 散 傅里葉 變 換（η0,η1,… ,ηp-1） 的DFT-leader-vector為[0；0,0,1,0]，或通過式（17）則選為[1；0,0,1,0]。 通過類似的計算，即得所要證明的結果。

證畢。

最后，考慮由式（3）定義的 Hall六次剩余序列（su） 的k-錯線性復雜度。由[6, Lemma 1]知，當因 此 ， 當p≡-1（mod 8） 時 ，下面分析ord（2）取最大的情況。

命題 12由式（3）定義的Hall六次剩余序列（su）在F2上的k-錯線性復雜度如下。

證明當p≡-1（m o d 8）時，由命題 4可知，（su） 的 離 散 傅 里 葉 變 換（ρ0,ρ1, … ,ρp-1） 的DFT-leader-vector為[1；0,0,0,1,0,0]。選擇錯誤序列（eu） 的離 散 傅 里 葉 變 換（η0,η1,… ,ηp-1） 的DFT-leadervector為[1；0,0,1,1,0,0]，則可計算得出eu。

因此，可以找到一個錯誤序列（eu）滿足使得序列（s）的線性復雜度從u從而完成了第一種情況的證明。而對于第二種情況，則由命題4和命題1即得。

證畢。

4 結束語

本文分別利用 Legendre序列、Ding-Helleseth-Lam序列和Hall六次剩余序列的離散傅里葉變換確定這些序列的1-錯線性復雜度，并在特定條件下得到這些序列的k-錯線性復雜度的部分結果，其中k＞1且d為小的正整數。

認為考慮一般的ordp（2）和適當大的k的情況是一個具有挑戰性的工作。若錯誤序列（eu）的滿足a0∈F2且對其他那么（eu） 可通過如式（18）所示的跡函數的和計算得到。