关于二元割圆序列的k-错线性复杂度

doi:10.11959/j.issn.1000-436x.2019034

通信学报 ›› 2019, Vol. 40 ›› Issue (2): 197-206.doi: 10.11959/j.issn.1000-436x.2019034

• 学术通信 • 上一篇

关于二元割圆序列的k-错线性复杂度

陈智雄¹,吴晨煌^1,²()

¹ 莆田学院福建省高校应用数学重点实验室，福建莆田 351100
² 电子科技大学计算机科学与工程学院，四川成都 611731

修回日期:2019-01-17 出版日期:2019-02-01 发布日期:2019-03-04
作者简介:陈智雄（1972– ），男，福建莆田人，博士，莆田学院教授,主要研究方向为序列密码。|吴晨煌（1981– ），男，福建莆田人，莆田学院副教授，电子科技大学博士生，主要研究方向为序列密码。
基金资助:
国家自然科学基金资助项目(61772292);国家自然科学基金国际合作交流基金资助项目(6181101289);福建省自然科学基金资助项目(2018J01425);福建省高校创新团队培育计划基金资助项目(2018-49)

k-error linear complexity of binary cyclotomic generators

Zhixiong CHEN¹,Chenhuang WU^1,²()

¹ Provincial Key Laboratory of Applied Mathematics,Putian University,Putian 351100,China
² School of Computer Science and Engineering,University of Electronic Science and Technology of China,Chengdu 611731,China

Revised:2019-01-17 Online:2019-02-01 Published:2019-03-04
Supported by:
The National Natural Science Foundation of China(61772292);Projects of International Cooperation and Exchanges NSFC(6181101289);The Natural Science Foundation of Fujian Province(2018J01425);Program for Innovative Research Team in Science and Technology in Fujian Province University(2018-49)

摘要/Abstract

摘要：

应用伪随机序列的离散傅里叶变换，讨论了周期为素数p的Legendre序列、Ding-Helleseth-Lam 序列及Hall六次剩余序列的k-错线性复杂度。具体地，首先确定了上述3种序列的1-错线性复杂度，其次对k≥2，以及2模p的阶的一些特殊取值，讨论了相应序列的k-错线性复杂度。

关键词: Legendre序列, Ding-Helleseth-Lam序列, Hall六次剩余序列, k-错线性复杂度, 离散傅里叶变换

Abstract:

In terms of the discrete Fourier transforms,the k-error linear complexities over F₂were discussed for Legendre,Ding-Helleseth-Lam,and Hall's sextic residue sequences of odd prime period p.More precisely,the 1-error linear complexities of these sequences were determined.Then,with some special restrictions of the order of 2 modulo p,partial results on their k-error linear complexities (k≥2) were proved.

Key words: Legendre sequence, Ding-Helleseth-Lam sequence, Hall's sextic residue sequence, k-error linear complexity, discrete Fourier transform

中图分类号:

TP309

陈智雄,吴晨煌. 关于二元割圆序列的k-错线性复杂度[J]. 通信学报, 2019, 40(2): 197-206.

Zhixiong CHEN,Chenhuang WU. k-error linear complexity of binary cyclotomic generators[J]. Journal on Communications, 2019, 40(2): 197-206.

参考文献 35

[1]	CUSICK T , DING C , RENVALL A . Stream ciphers and number theory[M]. Elsevier, 2004.
[2]	DING C . Pattern distributions of Legendre sequences[J]. IEEE Transactions on Information Theory, 1998,44(4): 1693-1698.
[3]	DING C , HELLESETH T , SHAN W . On the linear complexity of Legendre sequences[J]. IEEE Transactions on Information Theory, 1998,44(3): 1276-1278.
[4]	KIM J , SONG H . Trace representation of Legendre sequences[J]. Designs,Codes and Cryptography, 2001,24(3): 343-348.
[5]	DING C , HELLESETH T , LAM K . Several classes of binary sequences with three-level autocorrelation[J]. IEEE Transactions on Information Theory, 1999,45(7): 2606-2612.
[6]	KIM J , SONG H . On the linear complexity of Hall's sextic residue sequences[J]. IEEE Transactions on Information Theory, 2001,47(5): 2094-2096.
[7]	KIM J , SONG H , GONG G . Trace function representation of Hall's sextic residue sequences of period p≡7(mod 8)[M]. NewYork: Kluwer Academic Publishers, 2003,23-32.
[8]	CAI Y , DING C . Binary sequences with optimal autocorrelation[J]. Theoretical Computer Science, 2009,410(24-25): 2316-2322.
[9]	DING C , HELLESETH T . On cyclotomic generator of orderr[J]. Information Processing Letters, 1998,66(1): 21-25.
[10]	WANG Q , LIN D , GUANG X . On the linear complexity of Legendre sequences over F_g[J]. IEICE Transactions on Fundamentals of Electronics,Communications and Computer Sciences, 2014,97(7): 1627-1630.
[11]	HOFER R , WINTERHOF A . On the arithmetic autocorrelation of the Legendre sequence[J]. Advances in Mathematics of Communications, 2017,11(1): 237-244.
[12]	DU X , CHEN Z . A generalization of the Hall's sextic residue sequences[J]. Information Sciences, 2013,222: 784-794.
[13]	XIONG H , QU L , LI C . A new method to compute the 2-adic complexity of binary sequences[J]. IEEE Transactions on Information Theory, 2014,60(4): 2399-2406.
[14]	SU W , YANG Y , FAN C . New optimal binary sequences with period 4p via interleaving Ding-Helleseth-Lam sequences[J]. Designs,Codes and Cryptography, 2018,86(6): 1329-1338.
[15]	WHITEMAN A . A family of difference sets[J]. Journal of Mathematics., 1962,6(1): 107-121.
[16]	DING C , HELLESETH T . New generalized cyclotomy and its applications[J]. Finite Fields and their Applications, 1998,4(2): 140-166.
[17]	ZENG X , CAI H , TANG X ,et al. Optimal frequency hopping sequences of odd length[J]. IEEE Transactions on Information Theory, 2013,59(5): 3237-3248.
[18]	刘龙飞, 杨凯, 杨晓元 . 新的周期为p^m的GF(h)上广义割圆序列的线性复杂度[J]. 通信学报, 2017,38(9): 39-45.
	LIU L F , YANG K , YANG X Y . On the linear complexity of a new generalized cyclotomic sequence with length p^mover GF(h)[J]. Journal on Communications, 2017,38(9): 39-45.
[19]	XIAO Z , ZENG X , LI C ,et al. New generalized cyclotomic binary sequences of period p²[J]. Designs,Codes and Cryptography, 2018,86(7): 1483-1497.
[20]	CHEN Z , EDEMSKIY V , KE P ,et al. On k -error linear complexity of pseudorandom binary sequences derived from Euler quotients[J]. Advances in Mathematics of Communications, 2018,12(4): 805-816.
[21]	WU C , XU C , Chen Z ,et al. On error linear complexity of new generalized cyclotomic binary sequences of period p²[J]. Information Processing Letters, 2019,144: 9-15.
[22]	CHEN Z , NIU Z , WU C . On the k -error linear complexity of binary sequences derived from polynomial quotients[J]. Science China Information Sciences, 2015,58(9): 1-15.
[23]	ALY H , MEIDL W , WINTERHOF A . On the k-error linear complexity of cyclotomic sequences[J]. Journal of Mathematical Cryptology, 2007,1(3): 283-296.
[24]	ALY H , WINTERHOF A . On the k -error linear complexity over F_pof Legendre and Sidel'nikov sequences[J]. Designs,Codes and Cryptography, 2006,40(3): 369-374.
[25]	DING C , . Binary cyclotomic generators[C]// Fast Software Encryption-FSE'95. 1995: 29-60.
[26]	STAMP M , MARTIN C . An algorithm for the k-error linear complexity of binary sequences with period 2ⁿ[J]. IEEE Transactions on Information Theory, 1993,39(4): 1398-1401.
[27]	DING C , XIAO G , SHAN W . The stability theory of stream ciphers[M]. Berlin: Springer-VerlagPress, 1991.
[28]	MASSEY J . Codes and ciphers:Fourier and Blahut[M]. Boston: SpringerPress, 1998: 105-119.
[29]	MASSEY J , SERCONEK S . A Fourier transform approach to the linear complexity of nonlinearly filtered sequences[C]// Annual International Cryptology Conference.Springer. 1994: 332-340.
[30]	BLAHUT R . Transform techniques for error control codes[J]. IBM Journal of Research and development, 1979,23(3): 299-315.
[31]	MACWILLIAMS F , SLOANE N . The theory of error-correcting codes[M]. Amsterdam: ElsevierPress, 1977.
[32]	DAI Z , GONG G , SONG H ,et al. Trace representation and linear complexity of binary e th power residue sequences of period p[J]. IEEE Transactions on Information Theory, 2011,57(3): 1530-1547.
[33]	ALECU A , SALAGEAN A . An approximation algorithm for computing the k-error linear complexity of sequences using the discrete fourier transform[C]// IEEE International Symposium on Information Theory,2008, 2008, 2414-2418.
[34]	SALAGEAN A , ALECU A . An improved approximation algorithm for computing the k-error linear complexity of sequences using the discrete fourier transform[C]// International Conference on Sequences and their Applications. 2010: 151-165.
[35]	DING C , YANG J . Hamming weights in irreducible cyclic codes[J]. Discrete Mathematics, 2013,313(4): 434-446.

关于二元割圆序列的k-错线性复杂度

k-error linear complexity of binary cyclotomic generators

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

参考文献 35

相关文章 4

Metrics

推荐阅读 0

[1]	李玉博,陈邈,刘涛,张颖. 长度为奇素数的完备高斯整数序列构造法[J]. 通信学报, 2018, 39(11): 190-197.
[2]	邓峰，鲍长春，鲍枫. 基于AAC比特流的音频信号Hiss噪声抑制方法[J]. 通信学报, 2013, 34(5): 3-30.
[3]	邓峰,鲍长春,鲍枫. 基于AAC比特流的音频信号Hiss噪声抑制方法[J]. 通信学报, 2013, 34(5): 20-30.
[4]	何贤芒. Legendre序列在GF(p)上的线性复杂度[J]. 通信学报, 2008, 29(3): 16-22.