一類推廣的二元Legendre-Sidelnikov序列的自相關分布

柯品惠　　葉智釩　　常祖領(福建省網絡安全與密碼技術重點實驗室　福州　350117)(鄭州大學數學與統(tǒng)計學院　鄭州　450001)

?

一類推廣的二元Legendre-Sidelnikov序列的自相關分布

柯品惠*①葉智釩①常祖領②
①(福建省網絡安全與密碼技術重點實驗室福州350117)
②(鄭州大學數學與統(tǒng)計學院鄭州450001)

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

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

1　引言

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

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

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

2　預備知識

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

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

通過改變P和Q對應下標集的序列元素的值，文獻[15]構造了一類新的二元Legendre-Sidelnikov序列。

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

因此，引理中的第1個等式成立。

對于第2個等式，我們有

3　推廣的二元Legendre-Sidelnikov序列的周期自相關分布

利用上文已給定的符號，文獻[14]推廣的二元Legendre-Sidelnikov序列可以等價地定義為

平衡性是Golomb 3條隨機性假設之一，即對于一個周期為偶數的二元序列，序列中0與1的個數是相同的[1]。注意到，在文獻[14]亦指出了廣義Legendre-Sidelnikov序列是平衡性的，但沒有給出證明。為完整起見，下面給出一個簡要的證明。

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

那么，

進一步地，由中國剩余定理可知

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

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

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

進一步地，由引理1可知

同理，我們有

(2)若l∈Q*，則

同理，由引理1得

最后，

(3)若 l∈R，則

通過上述分析及引理1，我們有

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

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

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

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

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

因此，在p≡3(mod4)，q＞＞ p時，式(4)對應的序列的自相關性質比較好。 而p和q相差不大時，式(1)對應的序列的自相關性質比較好。

例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]。

對應地，它們的周期自相關分布如下：

[-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　結束語

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

參考文獻

[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]陳曉玉，許成謙，李玉博.新的完備高斯整數序列的構造方法[J].電子與信息學報，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的二元廣義分圓序列的線性復雜度[J].電子與信息學報，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]岳曌，高軍濤，謝佳.雙素數Sidel’nikov序列的自相關函數[J].電子與信息學報，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年生，副教授，主要研究方向為編碼密碼學.

葉智釩：男，1991年生，碩士生，研究方向為序列設計.

常祖領：男，1976年生，副教授，主要研究方向為編碼密碼學.

Autocorrelation Distribution of Binary Generalized Legendre-Sidelnikov Sequences

KE Pinhui①YE Zhifan①CHANG Zuling②
①(Fujian Provincial Key Laboratory of Network Security and Cryptology，Fuzhou 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

基金項目：福建師范大學“網絡與信息安全關鍵理論和技術”校創(chuàng)新團隊(IRTL1207)，福建省自然科學基金(2015J01237)，國家自然科學基金聯合基金(U1304604)

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

收稿日期：2015-06-08；改回日期：2015-09-11；網絡出版：2015-11-19

DOI:10.11999/JEIT150687

中圖分類號：TN918.1

文獻標識碼：A

文章編號：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)