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

王 艷 相乃姣 韓西林 閆聯(lián)陶

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

1 引言

偽隨機(jī)序列在流密碼、擴(kuò)頻通信、雷達(dá)導(dǎo)航、全球定位等領(lǐng)域中都有著極為重要的應(yīng)用[1]。偽隨機(jī)序列的密碼學(xué)性質(zhì)，如周期性、相關(guān)性、線性復(fù)雜度、2-adic復(fù)雜度等直接影響著一個(gè)流密碼算法的安全強(qiáng)度。其中線性復(fù)雜度是衡量偽隨機(jī)序列性質(zhì)的一個(gè)重要指標(biāo)，根據(jù)Berlekamp-Massey(B-M)算法，若一個(gè)偽隨機(jī)序列的線性復(fù)雜度大于其周期長度的1/2，則可稱其為一個(gè)好的偽隨機(jī)序列。

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

2 基礎(chǔ)知識(shí)

設(shè)p是奇素?cái)?shù)，g是奇數(shù)，且g是模p,2p,p2和2p2的公共本原元。記模2p2的剩余類環(huán)為Z2p2=

對(duì)i=0,1,令

3 主要結(jié)論及證明

3.1 主要定理及輔助引理

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

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

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

3.2 定理1的證明

注如果r|p-4且r|p-2，那么有p ≡4(modr),p≡2(modr)，則4≡2(modr),2≡0(modr)。因?yàn)閞為奇素?cái)?shù)，且r ≥5，所以這兩種情況不同時(shí)發(fā)生。

通過使用Magma，我們計(jì)算下面的例子來驗(yàn)證本文的結(jié)果。

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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