Fq上一類周期為2p2的四元廣義分圓序列的線性復雜度

王 艷 相乃姣 韓西林 閆聯陶

(西安建筑科技大學理學院 西安 710055)

1 引言

偽隨機序列在流密碼、擴頻通信、雷達導航、全球定位等領域中都有著極為重要的應用[1]。偽隨機序列的密碼學性質，如周期性、相關性、線性復雜度、2-adic復雜度等直接影響著一個流密碼算法的安全強度。其中線性復雜度是衡量偽隨機序列性質的一個重要指標，根據Berlekamp-Massey(B-M)算法，若一個偽隨機序列的線性復雜度大于其周期長度的1/2，則可稱其為一個好的偽隨機序列。

目前，已有大量的文獻研究了廣義分圓序列的線性復雜度。Ding[2]基于Whiteman廣義分圓理論構造了一類周期為pq的2元廣義分圓序列，并證明了這類序列具有高的線性復雜度和低的自相關性；Bai等人[3]基于Ding–Helleseth廣義分圓理論構造了一類新的周期為pq的2元廣義分圓序列，并確定了該類序列具有高的線性復雜度；李勝強等人[4]基于Whiteman廣義分圓理論，通過選取不同的特征集，構造了一類新的周期為pq的2元廣義分圓序列，得出該類序列的線性復雜度的下界為pq-p-q+1，并指出該類序列為平衡序列。Xiao等人[5]構造了一類新的周期為p2的2元廣義分圓序列，計算出了該類序列具有高的線性復雜度，最后提出了一類新的周期為pm的2元廣義分圓序列，并給出了一個關于其線性復雜度的猜想；隨后Edemskiy等人[6]證明了這個猜想，并將其結果推廣到了更一般的情形；Ouyang等人[7]基于Edemskiy等人的工作構造了兩類周期為2pm的2元廣義分圓序列，并給出了其線性復雜度的取值范圍，結果表明這兩類序列都具有好的線性復雜度性質。王艷等人[8]研究了一類新的周期為2pm的q階2元廣義分圓序列，并證明了該類序列具有高的線性復雜度；Wang等人[9]構造了F4上的一類周期為2pmqn的4元廣義分圓序列，證明了該類序列的線性復雜度可以達到最大；Ke等人[10]構造了兩類新的周期為2pm的4元廣義分圓序列，分別確定了這兩類序列在F4和Z4上都具有高的線性復雜度。Du等人[11]研究了F4上的周期為2p的4元廣義分圓序列的線性復雜度，結果表明其最小值為p+1；Chen等人[12]確定了Z4上 的周期為2p的4元廣義分圓序列的線性復雜度，結果表明其最小值為p；杜小妮等人[13]在Chen的基礎上進行了推廣，給出了Z4上周期為2p2的4元廣義分圓序列的線性復雜度，結果表明該類序列具有好的線性復雜度性質。本文基于文獻[13]構造的序列，構造了一類Fq上的周期為2p2的 4元廣義分圓序列，并計算了該類序列在Fq上的極小多項式和線性復雜度。本文結構安排如下：第2節給出了Fq上 一類周期為2p2的4元廣義分圓序列；第3節確定了該類序列在Fq上的極小多項式和線性復雜度；第4節對文章的工作做了小結和展望。

2 基礎知識

設p是奇素數，g是奇數，且g是模p,2p,p2和2p2的公共本原元。記模2p2的剩余類環為Z2p2=

對i=0,1,令

3 主要結論及證明

3.1 主要定理及輔助引理

定理1設r為奇素數，且滿足r ≥5,r/=p,m=ordp2(r)，并設β為擴域Frm上的2p2次單位根。由式(3)定義的周期為2p2的4 元廣義分圓序列{s(t)}在Frm上的線性復雜度為

根據引理6、引理7和引理10知η0+η1=0，且η0η1=0，所以得η0=η1=0。 證畢

序列{s(t)}的生成多項式為

3.2 定理1的證明

注如果r|p-4且r|p-2，那么有p ≡4(modr),p≡2(modr)，則4≡2(modr),2≡0(modr)。因為r為奇素數，且r ≥5，所以這兩種情況不同時發生。

通過使用Magma，我們計算下面的例子來驗證本文的結果。

例1設p=5,g=3,r=7，則周期為50的4元廣義分圓序列為003121213030312121303031222130-30312121303031212130。

由Magma計算得LC(s)=2p2-p+1=92，且r,p符合文中的第(1 2)種情況+p-2且2且r/|p-4且r/|p-2。

例2設p=7,g=3,r=5，則周期為98的4元廣義分圓序列為0031312130202130313121302021 30313121302021303131223020213031312130202130 31312130202130313121302021。

由Magma計算得LC(s)=2p2-p+1=92，且r,p符合文中的第(4)種情況r|p-2。

例3設p=7,g=3,r=11，則由Magma計算得LC(s)=2p2=98,且r,p符合文中的第(12)種情況+p-2且2且r/|p-4且2。

例4設p=11,g=7,r=17，則周期為242的4元廣義分圓序列為00302031303121202131213030 20313031212021312130302031303121202131213030 20313031212021312130302031303121202131213030 20313033212021312130302031303121202131213030 20313031212021312130302031303121202131213030 2031303121202131213030203130312120213121。

由Magma計算得LC(s)=2p2-1=241，且r,p符合文中的第(2)種情況r

例5設p=17,g=3,r=7，則周期為578的4元廣義分圓序列為0031312130212020313020212031 21313030313121302120203130202120312131303031 31213021202031302021203121313030313121302120 20313020212031213130303131213021202031302021 20312131303031312130212020313020212031213130 30313121302120203130202120312131303031312130 21202031302021203121313030313121302120203330 20212031213130303131213021202031302021203121 31303031312130212020313020212031213130303131 21302120213020212031213130303131213021202031 30202120312131303031312130212020313020212031 21313030313121302120203130202120312131303031 31213021202031302021203121313030313121302120 20313020212031213130。

由Magma計算得LC(s)=2p2-2=576，且r,p符合文中的第(5)種情況r|3p2+p-2且r|p2-2。

4 結束語

本文基于杜小妮等人[13]的工作，構造了一類周期為2p2的4元廣義分圓序列，研究了這類序列在Fq上的極小多項式和線性復雜度。結果表明，這類序列在Fq上的線性復雜度的最小值為2p2-p-1，大于其周期的1/2，即這類序列有高的線性復雜度，能夠有效地抵抗B-M算法的攻擊。后期研究該類序列4-adic復雜度也將是有意義的工作。