大线性复杂度三值自相关的二元三阶分圆序列的构造  

Construction of binary three-order cyclotomic sequences with 3-valued autocorrelation and large linear complexity

作　　者：李胜华[1] 赵晗诺[1,2] 罗炼飞 

机构地区：[1]湖北大学数学与统计学学院,武汉430062 [2]陕西国际商贸学院商学院,陕西咸阳712046

出　　处：《计算机应用》2015年第9期2542-2545,2552,共5页journal of Computer Applications

基　　金：湖北省教育厅中青年项目(Q20101004);应用数学湖北省重点实验室开放基金资助项目(O24017)

摘　　要：对于一类周期为素数p,p≡1(mod 3)的二元三阶分圆序列提出了一种构造方法,确保其少自相关值及大线性复杂度。利用分圆的知识计算其自相关值,并进一步考虑序列的自相关值为三值时,素数p应满足的条件。此时p应满足p=a2+12,a为整数。当p满足此形式时,序列的线性复杂度为p-1,否则为2(p-1)/3。通过计算机实验,找出了满足所给形式的p,并能生成对应的序列集,验证了序列的自相关性及线性复杂度。新序列的线性复杂度和已有的三元三阶分圆序列的相同;和二元偶数阶分圆序列的相比,大部分相同或较优(已有的有些情况为(p-1)/2、(p+1)/2或1+(p-1)/6)。所提出的构造方法可推广至其他少自相关值、大线性复杂度的奇数阶分圆序列集的构造上。大奇数阶分圆序列的平衡性也会提高,能被较好地应用于密码与通信系统中。In order to obtain the sequences with a few autocorrelation values and large linear complexity, a new class of binary cyclotomic sequences of order 3 with period p were constructed, where p is a prime and p≡ l（mod 3） . The autocorrelation was computed based on cyclotomy, and the condition for p that assures the 3-valued autocorrelation was discussed. The condition is thatp should be the formp = a2 ＋ 12 for an integer a. The linear complexity is p - 1 ifp is the form, or 2（p - 1）/3 otherwise. By computer experiments, all ps＇ satisfying the form were found, the corresponding sequences were given, and the autocorrelation and linear complexity were confirmed. The linear complexity was the same as that of the known ternary cyclotomic sequence of order 3. Compared with the related known binary cyclotomic sequences of even order, the linear complexity was the same or better in most cases. The method in this paper can be extended to construct other cyclotomic sequences of odd order with a few autocorrelation values and large linear complexity. Since the cyclotomic sequences of larger odd order also have better balance, they can be applied to stream ciphers and communication systems.

关 键 词：伪随机序列 分圆序列 分圆数 自相关值 极小多项式 线性复杂度 

分 类 号：TN918.1[电子电信—通信与信息系统]