一类p元序列集的相关性和线性复杂度的分析

《一类p元序列集的相关性和线性复杂度的分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第26卷第1期大学数学Vo1．26，№．12010年2月COLLEGEMATHEMATICSFeb．2O1O一类元序列集的相关性和线性复杂度的分析邢福弟，田金兵(海南师范大学初等教育学院，海南海口571158)[摘要]对于素数户和偶数一2k，构造了一类周期为户～1的声条序列组成的P元序列集s“，这里≠2(mod3)，r与p一1互素．利用d一齐次函数的性质，确定了这类序列集的相关函数取一1士，一1，一1+2·四值及相应分布；使用推广的Key方法证明了这类序列集具有较大的线性复杂度下界．这类序列集可适用于cDMA通信系统和密码系统中．[关键词]序列；相关函数；线性复杂度[中图分类号]TP3

2、09[文献标识码]A[文章编号]1672—1454(2010)01—0046—071前言具有低相关特性、大线性复杂度和大集合容量的伪随机序列在CDMA通信系统和密码系统中得到了重要应用，在CDMA通信系统中，具有低相关性的伪随机序列可降低来自同一信道中其他使用者的干扰，序列集合容量决定了CDMA通信系统的容量；在密码系统中，为了有效地抵抗互相关性攻击和基于Berlekamp-Massey算法实施的攻击，提高数据的安全性，要求所采用的伪随机序列不仅具有低相关特性，而且具有较大的线性复杂度．因此，设计同时具有低相关特性、大的线性复杂度和大的集合容量的序列集是一个重要研究课题．Klapper

3、提出d一齐次函数和d一齐次序列的概念，并给出了一种增大d一齐次序列的线性复杂度的方法[1]，它能从一个已知的d一齐次序列集获得具有相同相关性质的一类d一齐次序列集，而且其中某些集合的序列具有大的线性复杂度．例如人们利用d一型函数对小集合Kasami序列进行各种推广[1]，使得这些推广的序列集同小集合的Kasami序列一样具有优良的低相关性质，而且有大的线性复杂度，但是它们的集合容量相对于序列长度依然较小．最近，文献[4]构造了一类2”条周期为2”一1的低相关齐次序列集s“，这里n分别满足”三0(rood4)，通过取特殊的r值，证明了该序列具有较大的线性复杂度．对于素数户和偶数”，本文利

4、用齐次函数构造了一类周期为P一1容量为P的序列集S“，这里r与。一1互素．这类序列集不仅具有低相关特性，而且通过使用推广的Key方法[6]，证明了它具有较大的线性复杂度下界．特别地，当P一2时，本文给出的P元序列集即是文献[4]中的序列集，在文献[4]中，只是针对特殊的r值来讨论所构造的序列有较大的线性复杂度，但在本文中针对更具一般性的r计算出序列集的线性复杂度的上界和下界，并且可取任意素数．2预备知识定义1设域F是F的e次扩张(n—ek)，对于任意的a∈F，令[收稿日期]2007—08—20；[修改日期]2009—03—23[基金项目]国家自然科学基金(60963025)资助；海南省

5、自然基金项目(808152)；海南师范大学青年教师科研资助基金(QNO8O2)第1期邢福弟，等：一类P元序列集的相关性和线性复杂度的分析47r(a)一d，一。称tt一(a)为域F到F的迹函数．迹函数具有下列基本性质：(i)r(d)===fr(a’)Va∈F”，J一0。1，2，⋯；(ij)try',(“a+6)一atr'~(a)@btr~(卢)V“，6C-Fp，＆，∈Fp；(iii)V∈Ftr(a)一tr[fr(a)]．定义2没S是由M条周期为N的序列构成的序列集S一{{St)，0≤≤N一1}l0≤≤M一1}．s中的序列S(，)}和S，(f)}的周期互相关函数定义为、q1R(r)一∑sh

6、(t)sl(t+r)，其中0≤『j，／≤Ml，0≤r≤N一1，表示一个P次本原单位复根，t+r中的加法运算是模运算．当tz≠．R()被称为周期互相关函数；当万一z，R(r)被称为周期自相关函数，简写为Rh(r)．序列集的最大边峰值R⋯定义为R一max{IR(r)；I≠z或r≠0}．如果仔在．一个较小的常数c使得序列集s的最大边峰值R⋯满足R⋯≤c一，则称S具有低相关特性，或称之为低相关序列．定义3设H()是有限域F，上的函数．d是一个正整数，并且gcd(d，q一1)一1，若对任意的r∈F，干uY∈F有H()一H(z)，则称H(r)为从F到F—L的齐次函数．定义4I没H()为从F，到F。

7、(q—p“上的型函数，整数r满足gcd(r·q一1)一1，￡r(·)是从F，到F—L的迹数．a是F”的本原元．称一{(t)一tFj((H(e)))}为一条(，I齐次序列．对。-齐次序列，它的相关值分布具有如下性质：引理l设P≥2川一ek，，，、一(一1)／(p1)．1≤r．≤P一1，gcd(rd．一1)一1．令和7分别表示F和F的本原元．设序列{7z(y)一∑fr())具有两值自相关性，其中j是一个指标集，(一)，⋯，．／()是从F到F的一型函