The Linear Complexity of a New Class of Generalized Cyclotomic Sequence of Order q with Period 2pm
-
摘要: 该文基于Ding-广义分圆理论,将周期为
$ 2{p^m}$ ($ p$ 为奇素数,$ m$ 为正整数)广义分圆序列的研究推广到任意素数阶情形,构造了一类新序列。通过数论方法分析多项式广义分圆类,确定并计算线性复杂度与序列的2次剩余类和2次非剩余类的划分紧密相关。结果表明该类序列的线性复杂度远远大于周期的一半,能抗击应用Berlekamp-Massey(B-M)算法的安全攻击,是密码学意义上性质良好的伪随机序列。-
关键词:
- 广义分圆序列 /
- 线性复杂度 /
- 2次剩余类 /
- Berlekamp-Massey算法
Abstract: Based on the theory of Ding - generalized circle, a new class of generalized cyclotomic sequences of$ 2{p^m}$ ($ p$ odd prime and m>1) with arbitrary prime order is constructed in this paper. The polynomial cyclotomic classes are analysed by algebra number theory method. Moreover, the linear complexity of the new sequences are determined, which losely related to the division of quadratic residual classes and quadratic non-residual classes. Results show that the linear complexity of this kind of sequence is much larger than half of the period, hence, can fight Berlekamp-Massey’s security application attack that is a pseudo-random sequence with good properties in the sense of cryptography. -
GOLOMB S W and GONG Guang. Signal Design for Good Correlation: For Wireless Communication, Cryptography and Radar[M]. Cambridge: Cambridge University Press, 2005: 174–175. DING Cunsheng. Linear complexity of generalized cyclotomic binary sequences of order 2[J]. Finite Fields and Their Applications, 1997, 3(2): 159–174. doi: 10.1006/ffta.1997.0181 DING Cunsheng, HESSESETH T, and SHAN Weijuan. On the linear complexity of Legendre sequences[J]. IEEE Transactions on Information Theory, 1998, 44(3): 1276–1278. doi: 10.1109/18.669398 BAI Enjian, LIU Xiaojuan, and XIAO Guozhen. Linear complexity of new generalized cyclotomic sequences of order two of length pq[J]. IEEE Transactions on Information Theory, 2005, 51(5): 1849–1853. doi: 10.1109/TIT.2005.846450 YAN Tongjiang, LI Shengqiang, and XIAO Guozhen. On the linear complexity of generalized cyclotomic sequences with the period p m[J]. Applied Mathematics Letters, 2008, 21(2): 187–193. doi: 10.1016/j.aml.2007.03.011 DU Xiaoni, YAN Tongjiang, and XIAO Guozhen. Trace representation of some generalized cyclotomic sequences of length pq[J]. Information Sciences, 2008, 178(16): 3307–3316. doi: 10.1016/j.ins.2007.11.023 魏万银, 杜小妮, 王国辉. 周期为2pq的四元序列线性复杂度研究[J]. 计算机工程, 2016, 42(3): 161–164. doi: 10.3969/j.issn.1000-3428.2016.03.029WEI Wanyin, DU Xiaoni, and WANG Guohui. Research on linear complexity of quaternary sequences with period 2pq[J]. Computer Engineering, 2016, 42(3): 161–164. doi: 10.3969/j.issn.1000-3428.2016.03.029 杜小妮, 王国辉, 魏万银. 周期为2p2的四阶二元广义分圆序列的线性复杂度[J]. 电子与信息学报, 2015, 37(10): 2490–2494. doi: 10.11999/JEIT150180DU Xiaoni, WANG Guohui, and WEI Wanyin. Linear complexity of binary generalized cyclotomic sequences of order four with period 2p2[J]. Journal of Electronics &Information Technology, 2015, 37(10): 2490–2494. doi: 10.11999/JEIT150180 HU Liqin, YU Qin, and WANG Minhong. The linear complexity of Whiteman’s generalized cyclotomic sequences of period $ {p^{m + 1}}{q^{n + 1}}$ [J]. IEEE Transactions on Information Theory, 2012, 58(8): 5534–5543. doi: 10.1109/TIT.2012.2196254ZHANG Jingwei, ZHAO Chang’an, and MA Xiao. Linear complexity of generalized cyclotomic binary sequences of length 2p m[J]. Applicable Algebra in Engineering, Communication and Computing, 2010, 21(2): 93–108. doi: 10.1007/s00200-009-0116-2 TAN Lin, XU Hong, and QI Wenfeng. Remarks on the generalized cyclotomic sequences of length 2p m[J]. Applicable Algebra in Engineering, Communication and Computing, 2012, 23(5/6): 221–232. doi: 10.1007/s00200-012-0177-5 KE Pinhui, ZHANG Jie, and ZHANG Shengyuan. On the linear complexity and the autocorrelation of generalized cyclotomic binary sequences of length 2p n[J]. Designs, Codes and Cryptography, 2013, 67(3): 325–339. doi: 10.1007/s10623-012-9610-9 EDEMSKIY V and ANTONOVA O. The linear complexity of generalized cyclotomic sequences with period 2p n[J]. Applicable Algebra in Engineering, Communication and Computing, 2014, 25(3): 213–223. doi: 10.1007/s00200-014-0223-6 EDEMSKIY V. About computation of the linear complexity of generalized cyclotomic sequences with period p n+1[J]. Designs, Codes and Cryptography, 2011, 61(3): 251–260. doi: 10.1007/s10623-010-9474-9 刘龙飞, 杨凯, 杨晓元. 新的周期为p m的GF(h)上广义割圆序列的线性复杂度[J]. 通信学报, 2017, 38(9): 39–45. doi: 10.11959/j.issn.1000-436x.2017181LIU Longfei, YANG Kai, and YANG Xiaoyuan. On the linear complexity of a new generalized cyclotomic sequence with length p m over GF(h)[J]. Journal on Communications, 2017, 38(9): 39–45. doi: 10.11959/j.issn.1000-436x.2017181 XIAO Zibi, ZENG Xiangyong, LI Chunlei, et al. New generalized cyclotomic binary sequences of period p2[J]. Designs, Codes and Cryptography, 2018, 86(7): 1483–1497. doi: 10.1007/s10623-017-0408-7
点击查看大图
计量
- 文章访问数: 2053
- HTML全文浏览量: 861
- PDF下载量: 46
- 被引次数: 0