關(guān)于d元廣義Legendre-Sidelnikov序列的自相關(guān)性研究

申詩萌，劉華寧

(西北大學 數(shù)學學院，陜西 西安 710127)

具有良好偽隨機性質(zhì)的序列在通訊和密碼學上起著重要的作用,其中很多具有這些特性的序列是基于有限域的乘法特征來構(gòu)造的[1-8],包括Legendre序列、Sidelnikov序列和雙素數(shù)序列。Su和Winterhof結(jié)合這3個序列的概念構(gòu)造了一個新的Legendre-Sidelnikov序列[9],具體來說,設(shè)p是一個奇素數(shù),q是一個奇素數(shù)冪且滿足gcd(p,q-1)=1。令

m=p(q-1),

P={0,p, 2p,…,(q-2)p},

R={0,1,2,…,m-1}(P∪Q*),

Su和Winterhof研究了該序列的自相關(guān)性,給出了周期自相關(guān)的精確值和非周期自相關(guān)函數(shù)的一個上界, 并且注意到該序列僅在p=q時是平衡的[9]。文獻[10]研究了k階相關(guān)測度以及線性復雜度。此外, Su給出了該序列在不同條件下線性復雜度的上界和下界[11]。相關(guān)研究成果還可參考文獻[12]和文獻[13]。

χp(α)=ω,χp(0)=0，

χp(i)=χp(αj)=ωj，

(1)

對于周期為T的d元序列(si),周期自相關(guān)函數(shù)的定義為

其中1≤l

本文對于一般的d,完全給出d元廣義Legendre-Sidelnikov序列(1)的自相關(guān)值，主要結(jié)論見定理1。

定理1設(shè)(si)如序列(1)中的定義。則有

AC(si,l)=

1 關(guān)于特征和的一些引理

證明見文獻[14]中引理3。

證明見文獻[14]引理4。

2 定理1的證明

根據(jù)d元廣義Legendre-Sidelnikov序列(1)的定義,有

(2)

下面，分3種情形證明定理1。

情形1當l∈P{0}時,該情況在文獻[14]中得到了證明。

情形2當l∈Q*時,由式(2)得

ωsi-si+l=

因此

(3)

結(jié)合引理2，得到

(4)

以及

χp(-l)(-χq(-1)-1)。

(5)

再由引理1，可得

(6)

-χq(2)

(7)

以及

χq(-1)+1。

(8)

最后,結(jié)合式(3)至式(8)可直接得到

χq(2)χp(-l)+χp(-l)(-χq(-1)-1)-

χq(2)+χq(-1)+1=

情形3當l∈R時, 由式(2)得

ωsi-si+l=

根據(jù)引理1，得到

(9)

(10)

-χq(-g-l+1)。

(11)

再結(jié)合引理2，有

(12)

(13)

以及

(14)

當l滿足(q-1)|l時,結(jié)合式(9)、式(12)至式(14)，得到

(q-2)χp(-l)-(q-2)=

然而，當l∈R滿足(q-1)不整除l時,有

χp(-l)χq(-g-l+1)+

χp(-l)χq(-g-l+1)+

χq(g-l)+1=

綜上,即完成了定理1的證明。

3 結(jié)語

在文獻[14]中，Su利用乘法特征將一般的Legendre-Sidelnikov序列推廣成形為序列(1)的d元平衡序列,其中d是p-1和q-1的一個公共因子,并且gcd(p,q-1)=1。而本文的主要結(jié)果是進一步計算了該d元廣義Legendre-Sidelnikov序列的自相關(guān)值，并利用特征和的性質(zhì)證明了該序列有很好的自相關(guān)性質(zhì)，完整地解決了該序列自相關(guān)性的研究。