一類推廣的二元Legendre-Sidelnikov序列的自相關(guān)分布

柯品惠　　葉智釩　　常祖領(lǐng)(福建省網(wǎng)絡(luò)安全與密碼技術(shù)重點(diǎn)實(shí)驗(yàn)室　福州　350117)(鄭州大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院　鄭州　450001)

?

一類推廣的二元Legendre-Sidelnikov序列的自相關(guān)分布

柯品惠*①葉智釩①常祖領(lǐng)②
①(福建省網(wǎng)絡(luò)安全與密碼技術(shù)重點(diǎn)實(shí)驗(yàn)室福州350117)
②(鄭州大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院鄭州450001)

摘要：推廣的Legendre-Sidelnikov序列較之原序列有更好的平衡性質(zhì)，但是關(guān)于該序列的周期自相關(guān)函數(shù)，迄今僅知道一些特殊移位的情形。該文利用有限域上特征和的相關(guān)性質(zhì)，給出了推廣的二元Legendre-Sidelnikov序列的自相關(guān)函數(shù)的完整分布。結(jié)果表明當(dāng)p≡3(mod 4)且q? p時(shí)，推廣的Legendre-Sidelnikov序列較之原序列有更好的周期自相關(guān)函數(shù)的分布。

關(guān)鍵詞：Legendre序列；Sidelnikov序列；平衡性；周期自相關(guān)；乘法特征

1　引言

具有良好自相關(guān)特性的序列在通信系統(tǒng)、雷達(dá)和密碼學(xué)等應(yīng)用中起著重要的作用[1-4]。 許多具有這些特性的序列是利用有限域的乘法特征來(lái)構(gòu)造的。一個(gè)著名的例子是Legendre序列，該序列的構(gòu)造是基于有限域Fp上的二次特征，其中p為素?cái)?shù)。特別地，F(xiàn)2上的Legendre序列已被證明具有較高的線性復(fù)雜度和很好的偽隨機(jī)特性，具體可參看文獻(xiàn)[5，6]。 另一個(gè)例子就是Sidelnikov序列，該序列也已被證明有良好的周期自相關(guān)特性[7-10]。最近，結(jié)合以上兩個(gè)概念，文獻(xiàn)[11，12]構(gòu)造了一種新的序列——Legendre-Sidelnikov序列。文獻(xiàn)[11]給出了Legendre-Sidelnikov序列的一些偽隨機(jī)性質(zhì)，例如在p=q時(shí)該序列是平衡的，以及該序列的周期自相關(guān)分布和非周期自相關(guān)分布。進(jìn)一步地，文獻(xiàn)[12，13]分析了該序列的線性復(fù)雜度，并在某些特殊情況下給出了該序列線性復(fù)雜度的一個(gè)下界。

注意到Legendre-Sidelnikov序列僅在gcd(p，q -1)=1且p=q時(shí)是平衡的。為了改進(jìn)該序列的平衡性，即使得序列在更多的情形下都保持平衡性，人們對(duì)已有的Legendre-Sidelnikov序列進(jìn)行了改進(jìn)。一方面，利用有限域的乘法特征，文獻(xiàn)[14]把Legendre-Sidelnikov序列推廣到d元的情形，其中d 是p -1與q -1的公因子。此時(shí)，d元Legendre-Sidelnikov 序列對(duì)任意的奇素?cái)?shù)p 和奇素?cái)?shù)冪q(gcd(p，q -1)=1)都是平衡的，即d 元廣義Legendre-Sidelnikov 序列具有更好的平衡性。當(dāng)d =2時(shí)，與文獻(xiàn)[11]定義的序列比較易知，兩條序列在i∈R時(shí)取值相同，但是在i∈P和i∈Q*不同，前者取值為常數(shù)，而后者取值更隨機(jī)。 文獻(xiàn)[14]分析了該序列的一些重要的偽隨機(jī)性質(zhì)包括非周期自相關(guān)、k階相關(guān)性測(cè)度和線性復(fù)雜性等。另外，最近文獻(xiàn)[15]也通過(guò)改變P和Q對(duì)應(yīng)下標(biāo)集的序列元素的賦值，構(gòu)造了一類新的二元Legendre-Sidelnikov序列。與文獻(xiàn)[14]中的定義的序列比較易知，對(duì)下標(biāo)集Q對(duì)應(yīng)的序列值僅相差一個(gè)常數(shù)。 但是，對(duì)下標(biāo)集P對(duì)應(yīng)的序列元素，兩個(gè)構(gòu)造得到的序列是不相同的。同時(shí)，文獻(xiàn)[15]給出了該序列的自相關(guān)函數(shù)的分布，并指出該序列在一些情形具有較低的自相關(guān)性質(zhì)。

關(guān)于文獻(xiàn)[14]中的定義的d元廣義Legendre-Sidelnikov序列的周期自相關(guān)分布，迄今僅知道一個(gè)特殊情形，即序列移位是p的倍數(shù)的情形(文獻(xiàn)[14]引理5)。 一般地，該序列自相關(guān)函數(shù)分布的完全確定較為困難。本文研究了文獻(xiàn)[14]中推廣的二元Legendre-Sidelnikov序列，即d =2的情形，給出了該序列完整的周期自相關(guān)分布。具體地，本文安排如下：第2節(jié)給出了本文需要的一些定義和引理；第3節(jié)計(jì)算了推廣的二元Legendre-Sidelnikov序列的周期自相關(guān)分布；最后，對(duì)Legendre-Sidelnikov序列及其推廣的相關(guān)性進(jìn)行比較，并提供了相應(yīng)的實(shí)例。

2　預(yù)備知識(shí)

令n=p(q -1)，其中p為奇素?cái)?shù)，q為奇素?cái)?shù)冪且gcd(p，q -1)=1，以及，。注意到P∩ Q令。 定義上的Legendre-Sidelnikov序列如式(1)：

文獻(xiàn)[14]對(duì)上述概念進(jìn)行了推廣，給出了d元廣義Legendre-Sidelnikov序列的定義。令p為奇素?cái)?shù)q為奇素?cái)?shù)的冪次且q≡1(mod d)，g是有限域Fq的本原元。定義Fq上的d階乘法特征，，其中w是復(fù)數(shù)域上的d階單位根。則d元廣義Legendre-Sidelnikov序列定義為

通過(guò)改變P和Q對(duì)應(yīng)下標(biāo)集的序列元素的值，文獻(xiàn)[15]構(gòu)造了一類新的二元Legendre-Sidelnikov序列。

下面我們給出一些引理，這些引理將在正文的證明中被多次用到。

因此，引理中的第1個(gè)等式成立。

對(duì)于第2個(gè)等式，我們有

3　推廣的二元Legendre-Sidelnikov序列的周期自相關(guān)分布

利用上文已給定的符號(hào)，文獻(xiàn)[14]推廣的二元Legendre-Sidelnikov序列可以等價(jià)地定義為

平衡性是Golomb 3條隨機(jī)性假設(shè)之一，即對(duì)于一個(gè)周期為偶數(shù)的二元序列，序列中0與1的個(gè)數(shù)是相同的[1]。注意到，在文獻(xiàn)[14]亦指出了廣義Legendre-Sidelnikov序列是平衡性的，但沒(méi)有給出證明。為完整起見(jiàn)，下面給出一個(gè)簡(jiǎn)要的證明。

定理1式(4)定義的推廣的二元Legendre-Sidelnikov序列是平衡的。

那么，

進(jìn)一步地，由中國(guó)剩余定理可知

定理2式(4)定義的推廣的二元Legendre-Sidelnikov序列的周期自相關(guān)函數(shù)分布為

證明 根據(jù)l，0＜l＜ p(q -1)屬于P{0}，Q*或R，證明可分為如下3部分。

(1)若 l∈P{0}，則

進(jìn)一步地，由引理1可知

同理，我們有

(2)若l∈Q*，則

同理，由引理1得

最后，

(3)若 l∈R，則

通過(guò)上述分析及引理1，我們有

推論1 式(4)定義的推廣的二元Legendre-Sidelnikov序列的自相關(guān)函數(shù)的一個(gè)上界為。

注1 通過(guò)比較式(1)，式(3)和式(4)定義的序列的周期自相關(guān)函數(shù)的分布，不難發(fā)現(xiàn)在移位時(shí)，三者的周期自相關(guān)差別都不大。當(dāng)選取不同的p，q時(shí)，在移位l∈P或l≡0(modq -1)時(shí)產(chǎn)生了較大的區(qū)別。具體地，在q≡3(mod4)且移位l∈P時(shí)，式(1)，式(3)和式(4)定義的序列的自相關(guān)函數(shù)的分布分別為

在q≡1(mod4)且移位l∈P時(shí)，式(1)，式(3)和式(4)定義的序列的自相關(guān)函數(shù)的分布分別為

在p≡3(mod4)且移位l≡0(modq -1)時(shí)，式(1)，式(3)和式(4)定義的序列的自相關(guān)函數(shù)的分布分別為p-q -2，1-q與1-q。

在p≡1(mod4)且移位l≡0(modq -1)時(shí)，式(1)，式(3)和式(4)定義的序列的自相關(guān)函數(shù)的分布分別為p-q -2+2(l / p)，1-q與(q-1)(2(l / p)-1)。

因此，在p≡3(mod4)，q＞＞ p時(shí)，式(4)對(duì)應(yīng)的序列的自相關(guān)性質(zhì)比較好。 而p和q相差不大時(shí)，式(1)對(duì)應(yīng)的序列的自相關(guān)性質(zhì)比較好。

例1 令 p =3，q =23，式(1)，式(3)和式(4)定義的序列分別如下：

[1，0，1，1，1，0，1，0，0，1，1，0，1，1，0，1，0，1，1，0，1，1，0，1，1，1，0，1，0，1，1，0，0，1，1，0，1，1，1，1，1，1，1，1，1，1，0，0，1，1，1，1，1，1，1，0，0，1，1，0，1，0，0，1，0，0];

[1，0，1，0，1，0，1，0，0，0，1，0，1，1，0，0，0，1，1，0，1，0，0，1，1，1，0，0，0，1，1，0，0，0，1，0，1，1，1，0，1，1，1，1，1，0，0，0，1，1，1，0，1，1，1，1，0，0，1，0，1，0，0，0，0，0 ];

[0，0，1，1，1，0，0，0，0，0，1，1，1，1，0，1，0，1，1，0，1，1，0，1，0，1，0，1，0，1，1，0，0，0，1，0，1，1，1，0，1，1，0，1，1，0，0，0，1，1，1，0，1，1，1，0，0，1，1，0，0，0，0，0，0，0]。

對(duì)應(yīng)地，它們的周期自相關(guān)分布如下：

[-2，-2，22，2，-2，18，-2，2，22，2，-2，18，-2，-2，22，2，-2，18，-2，2，22，-22，-2，18，-2，-2，22，-2，-2，18，-2，-2，22，-2，-2，18，-2，-2，22，-2，-2，18，-2，-22，22，2，-2，18，-2，2，22，-2，-2，18，-2，2，22，2，-2，18，-2，2，22，-2，-2 ];

[-2，2，-18，2，2，18，-2，2，-26，2，2，18，2，2，-18，2，2，18，-2，2，-18，-22，-2，18，-2，2，-26，2，-2，18，2，2，-26，2，2，18，-2，2，-26，2，-2，18，-2，-22，-18，2，-2，18，2，2，-18，2，2，18，2，2，-26，2，-2，18，2，2，-18，2，-2 ];

[2，2，-6，2，-2，-6，2，2，6，2，-2，-6，-2，2，-6，2，-2，-6，2，2，-6，-22，2，-6，2，2，6，2，2，-6，-2，2，6，2，-2，-6，2，2，6，2，2，-6，2，-22，-6，2，2，-6，-2，2，-6，2，-2，-6，-2，2，6，2，2，-6，-2，2，-6，2，2]。

4　結(jié)束語(yǔ)

對(duì)于任意的奇素?cái)?shù)p和奇素?cái)?shù)的冪次q且 gcd(p，q -1)=1，由于Ledendre-Sidelnikov序列在支撐集為P與Q*時(shí)取值總是固定的，所以它僅在p=q時(shí)是平衡的。而推廣的Ledendre-Sidelnikov序列在該部分是利用二次剩余來(lái)賦值。因此，推廣的Ledendre-Sidelnikov序列總是平衡的，同時(shí)具有更好的的偽隨機(jī)性質(zhì)。本文給出了推廣的二元Legendre-Sidelnikov序列自相關(guān)函數(shù)的分布。由結(jié)果可以看出，當(dāng)p≡3(mod4)，q＞＞ p時(shí)，推廣后的序列與原來(lái)的相比有更優(yōu)的周期自相關(guān)函數(shù)的分布。

參考文獻(xiàn)

[1]GOLOMB G and GONG G.Signal Designs with Good Correlations:Forwireless Communications，Cryptography and Radar Applications[M].Cambridge，U.K.:Cambridge University Press，2005:174-175.

[2]ARASU K T，DING C，HELLESETH T，et al.Almost difference sets and their sequences with optimal autocorrelation[J].IEEE Transactions on Information Theory，2001，47(7):2934-2943.

[3]陳曉玉，許成謙，李玉博.新的完備高斯整數(shù)序列的構(gòu)造方法[J].電子與信息學(xué)報(bào)，2014，36(9):2081-2085.doi:10.3724/SP.J.1146.2103.01697.CHEN Xiaoyu，XU Chengqian，and LI Yubo.New constructions of perfect Gaussian integer sequences[J].Journal of Electronics ＆ Information Technology，2014，36(9):2081-2085.doi:10.3724/SP.J.1146.2103.01697.

[4]李瑞芳，柯品惠.一類新的周期為2pq的二元廣義分圓序列的線性復(fù)雜度[J].電子與信息學(xué)報(bào)，2014，36(3):650-654.doi:10.3724/SP.J.1146.2103.00751.LI Ruifang and KE Pinhui.The linear complexity of a new class of generalized cyclotomic sequence with period 2pq[J].Journal of Electronics ＆ Information Technology，2014，36(3):650-654.doi:10.3724/SP.J.1146.2103.00751.

[5]DING C，HELLESETH T，and SAN W.On the linear complexity of Legendre sequences[J].IEEE Transactions on Information Theory，1998，44(3):1276-1278.

[6]DING C.Pattern distributions of Legendre sequences[J].IEEE Transactions on Information Theory，1998，44(4):1693-1698.

[7]SIDELNIKOV V M.Some k-valued pseudo-random sequences and nearly equidistant codes[J].Problems of Information Transmission，1969，5(1):12-16.

[8]岳曌，高軍濤，謝佳.雙素?cái)?shù)Sidel’nikov序列的自相關(guān)函數(shù)[J].電子與信息學(xué)報(bào)，2013，35(11):2602-2607.doi:10.3724/ SP.J.1146.2103.00147.YUE Zhao，GAO Juntao，and XIE Jia.Autocorrelation of the two-prime Sidel’nikov sequence[J].Jounal of Electronics ＆Information Technology，2013，35(11):2602-2607.doi:10.3724/SP.J.1146.2103.00147.

[9]KIM Youngtae，SONG Minkyu，KIM Daesan，et al.Properties and crosscorrelation of decimated sidelnikov sequences[J].IEICE Transactions on Fundamentals，2014，97-A(12):2562-2566.

[10]KIM Youngtae，KIM Daesan，and SONG Hongyeop.New M-Ary sequence families with low correlation from the array structure of sidelnikov sequences[J].IEEE Transactions on Information Theory，2015，61(1):655-670.

[11]SU M and WINTERHOF A.Autocorrelation of Legendre-Sidelnikov sequences[J].IEEE Transactions on Information Theory，2010，56(4):1714-1718.

[12]SU M.On the linear complexity of Legendre-Sidelnikov sequences[J].Design Codes and Cryptography,2015，74(3):703-717.

[13]SU M and WINTERHOF A.Correlation measure of order k and linear complexity profile of legendre-sidelnikov sequences[C].Proceedings of Fifth International Workshop on Signal Design and its Applications in Communications，Guilin，China，2011:6-8.

[14]SU M.ON the d-ary Generalized Legendre-Sidelnikov Sequence[J].LNCS，2012，7280:233-244.

[15]YAN T，LIU H，and SUN Y.Autocorrelation of modified Legendre-Sidelnikov sequences[J].IEICE Transactions on Fundamentals，2015，E98-A(2):771-775.

[16]BURTON D M.Elementary Number Theory[M].Maidenhead:UK，McGraw-Hill Education Press，1998:92-105.

[17]LIDL R and NIEDERREITER H.Finite Fields[M].MA:Addision-Wesley，1983:217-225.

柯品惠：男，1978年生，副教授，主要研究方向?yàn)榫幋a密碼學(xué).

葉智釩：男，1991年生，碩士生，研究方向?yàn)樾蛄性O(shè)計(jì).

常祖領(lǐng)：男，1976年生，副教授，主要研究方向?yàn)榫幋a密碼學(xué).

Autocorrelation Distribution of Binary Generalized Legendre-Sidelnikov Sequences

KE Pinhui①YE Zhifan①CHANG Zuling②
①(Fujian Provincial Key Laboratory of Network Security and Cryptology，F(xiàn)uzhou 350117，China)
②(School of Mathematics and Statistics，Zhengzhou University，Zhengzhou 450001，China)

Abstract:Compared with the original Legendre-Sidelnikov sequence，the generalized Legendre-Sidelnikov sequence has a better balanced property.For its autocorrelation distribution，however，only some special cases are known.In this paper，using the character sums，the autocorrelation distribution of the generalized binary Legendre-Sidelnikov sequence is determined completely.The result shows that the generalized Legendre-Sidelnikov sequence possesses a better autocorrelation distribution if p≡3(mod 4)and q? p.

Key words:Legendre sequence; Sidelnikov sequence; Balance; Periodic autocorrelation; Multiplicative character

基金項(xiàng)目：福建師范大學(xué)“網(wǎng)絡(luò)與信息安全關(guān)鍵理論和技術(shù)”校創(chuàng)新團(tuán)隊(duì)(IRTL1207)，福建省自然科學(xué)基金(2015J01237)，國(guó)家自然科學(xué)基金聯(lián)合基金(U1304604)

*通信作者：柯品惠keph@fjnu.edu.cn

收稿日期：2015-06-08；改回日期：2015-09-11；網(wǎng)絡(luò)出版：2015-11-19

DOI:10.11999/JEIT150687

中圖分類號(hào)：TN918.1

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-5896(2016)02-0303-07

Foundation Items:Fujian Normal University Innovative Research Team(IRTL1207)，Natural Science Foundation of Fujian Province(2015J01237)，The Joint Funds of the National Natural Science Foundation of China(U1304604)