周期为p2的q元序列的k–错线性复杂度

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

通信学报 ›› 2019, Vol. 40 ›› Issue (12): 21-28.doi: 10.11959/j.issn.1000-436x.2019230

周期为p²的q元序列的k–错线性复杂度

吴晨煌^1,²,许春香¹,杜小妮³

¹ 电子科技大学计算机科学与工程学院，四川成都 611731
² 莆田学院应用数学福建省高校重点实验室，福建莆田 351100
³ 西北师范大学数学与统计学院，甘肃兰州730070

修回日期:2019-11-02 出版日期:2019-12-25 发布日期:2020-01-16
作者简介:吴晨煌（1981– ），男，福建莆田人，电子科技大学博士生，莆田学院副教授，主要研究方向为序列密码|许春香（1965– ），女，湖南长沙人，博士，电子科技大学教授、博士生导师，主要研究方向为信息安全、密码学及其应用。|杜小妮（1972– ），女，甘肃庆阳人，博士，西北师范大学数学与统计学院信息研究所副所长、博士生导师，主要研究方向为密码学、编码理论和信息安全。
基金资助:
国家自然科学基金资助项目(61772292);国家自然科学基金资助项目(61772022);国家自然科学基金资助项目(61872060);国家自然科学基金国际（地区）合作交流项目NSFC-RFBR(61911530130);福建省自然科学基金资助项目(2018J01425)

k-error linear complexity of q-ary sequence of period p²

Chenhuang WU^1,²,Chunxiang XU¹,Xiaoni DU³

¹ School of Computer Science and Engineering,University of Electronic Science and Technology of China,Chengdu 611731,China
² Provincial Key Laboratory of Applied Mathematics,Putian University,Putian 351100,China
³ College of Mathematics and Statistics,Northwest Normal University,Lanzhou 730070,China

Revised:2019-11-02 Online:2019-12-25 Published:2020-01-16
Supported by:
The National Natural Science Foundation of China(61772292);The National Natural Science Foundation of China(61772022);The National Natural Science Foundation of China(61872060);Projects of International Cooperation and Exchanges NSFC(61911530130);The Natural Science Foundation of Fujian Province(2018J01425)

摘要/Abstract

摘要：

基于矩阵中元素统计的方法，给出了计算周期为p2的q元序列k–错线性复杂度的新方法，其中，p,q为奇素数且q为模p2的本原元。给出了一个一般性的结论及其证明，并通过列举2类周期为p2的q元序列及其实例来验证结论的正确性。该方法不需要迭代计算，通过程序实现并与现有算法进行效率比较，结果表明所给出的新算法在计算周期为p2的q元序列的k–错线性复杂度方面效率明显更高。

关键词: 序列密码, q元序列, k–错线性复杂度, 费马商序列, 广义割圆序列

Abstract:

Based on element statistics in a matrix,a new efficient computing method for computing the k-error linear complexity of q-ary sequence of period p2was proposed,where p,q were odd primes and q modulo p2was primitive.A general result and a concrete proof were showed.To verify the correctness of the result,two kinds of q-ary sequence of period p2were illustrated.Because the new method does not need iterative calculation and when it is implemented by program and compared with existing algorithms,the results show that the proposed new algorithm is significantly more efficient in calculating k-error linear complexity of q-ary sequence of period p2.

Key words: stream cipher, q-ary sequence, k-error linear complexity, Fermat quotient sequence

中图分类号:

TP309

吴晨煌,许春香,杜小妮. 周期为p²的q元序列的k–错线性复杂度[J]. 通信学报, 2019, 40(12): 21-28.

Chenhuang WU,Chunxiang XU,Xiaoni DU. k-error linear complexity of q-ary sequence of period p²[J]. Journal on Communications, 2019, 40(12): 21-28.

图/表 2

参考文献 23

[1]	RUPPEL R . Analysis and design of stream ciphers[J]. Springer-Verlag, 1986.
[2]	CUSICK T , DING C , RENVALL A . Stream ciphers and number theory[M]. Amsterdam: North-Holland Publishing CompanyPress, 1998.
[3]	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): 1389-1401.
[4]	DING C , . Lower bounds on the weight complexity of cascaded binary sequences[C]// International Conference on Cryptology,Lecture Notes in Computer Science. 1991,453: 39-43.
[5]	DING C , XIAO G , SHAN W . The stability theory of stream ciphers[M]. Springer Science ＆ Business Media, 1991.
[6]	GOLOMB S , GONG G . Signal design for good correlation:for wireless communication,cryptography,and radar[M]. Cambridge University Press, 2005.
[7]	BERLEKAMP E . Algebraic coding theory[M]. New York: McGraw-HillPress, 1968.
[8]	MASSEY J . Shift register synthesis and BCH decoding[J]. IEEE Transactions on Information Theory, 1969,15(1): 122-127.
[9]	GAMES R , CHAN A . A fast algorithm for determining the complexity of a binary sequence with period 2ⁿ[J]. IEEE Transactions on Information Theory, 1983,29(1): 144-146.
[10]	MEIDL W . On the stability of 2ⁿ-periodic binary sequences[J]. IEEE Transactions on Information Theory, 2005,51(3): 1151-1155.
[11]	魏仕民, 白国强, 肖国镇 . 确定周期为pⁿ的二元周期序列的线性复杂度的一个快速算法[J]. 通信学报, 1999,20(8): 36-40.
	WEI S M , BAI G Q , XIAO G Z . A fast algorithm for determining the linear complexity of a binary sequence with period pⁿ[J]. Journal on Communications, 1999,20(8): 36-40.
[12]	王磊, 张玉清, 肖国镇 . 确定周期为pⁿ的二元序列的k-错线性复杂度的一个算法[J]. 通信学报, 2001,22(4): 91-95.
	WANG L , ZHANG Y Q , XIAO G Z . An algorithm for determining the k-error linear complexity of a binary sequence with period pⁿ[J]. Journal on Communications, 2001,22(4): 91-95.
[13]	陈智雄, 牛志华, 吴晨煌 . 周期为素数平方的二元序列的 k-错线性复杂度[J]. 密码学报, 2019,6(5): 574-584.
	CHEN Z X , NIU Z H , WU C H . On the k-error linear complexity of prime-square periodic binary sequences[J]. Journal of Cryptologic Research, 2019,6(5): 574-584.
[14]	XIAO G , WEI S , LAM K Y ,et al. A fast algorithm for determining the linear complexity of a sequence with period pⁿ over GF(q)[J]. IEEE Transactions on Information Theory, 2000,46(6): 2203-2206.
[15]	魏仕民, 董庆宽, 肖国镇 . 确定周期序列k-错复杂度的一个快速算法[J]. 西安电子科技大学学报, 2001,28(4): 421-424.
	WEI S M , DONG Q K , XIAO G Z . An efficient algorithm for the k-error linear complexity of periodic sequences[J]. Journal of Xidian University, 2001,28(4): 421-424.
[16]	白恩健, 刘晓娟, 肖国镇 . 确定周期为pⁿ的二元序列k-错复杂度曲线的快速算法[J]. 通信学报, 2004,25(10): 1-7.
	BAI E J , LIU X J , XIAO G Z . A fast algorithm for determining k-error linear complexity profile of a binary sequence with period pⁿ[J]. Journal on Communications, 2004,25(10): 1-7.
[17]	苏明, 符方伟 . 随机周期序列 k-错线性复杂度的期望上界[J]. 通信学报, 2005,26(2): 60-65.
	SU M , FU F W . Upper bound of expected value of the k-error linear complexity of random periodic sequences[J]. Journal on Communications, 2005,26(2): 60-65.
[18]	LIDL R , NIEDERREITER H . Finite fields[M]. Addison-Wesley, 1983.
[19]	CHEN Z , OSTAFE A , WINTERHOF A . Structure of pseudorandom numbers derived from Fermat quotients[C]// International Workshop on the Arithmetic of Finite Fields. Springer, 2010, 73-85.
[20]	CHEN Z , DU X . On the linear complexity of binary threshold sequences derived from Fermat quotients[J]. Designs,Codes and Cryptography, 2013,67(3): 317-323.
[21]	CHEN Z . Trace representation and linear complexity of binary sequences derived from Fermat quotients[J]. Science China Information Sciences, 2014,57(11): 1-10.
[22]	PARK K , SONG H , KIM D ,et al. Optimal families of perfect polyphase sequences from the array structure of fermat-quotient sequences[J]. IEEE Transactions on Information Theory, 2016,62(2): 1076-1086.
[23]	杜小妮, 李芝霞, 万韫琦 ,等. 基于费马商的 r 元序列的迹表示[J]. 电子学报, 2017,45(10): 2439-2442.
	DU X N , LI Z X , WAN Y Q ,et al. Trace representation of r-ary sequences derived from Fermat quotient[J]. Acta Electronicas Sinica, 2017,45(10): 2439-2442.

算法		平均运行时间/ms
算法	p²=49	p²=361	p²=961
文献[15]算法	0.112	0.897	2.447
本文算法	0.013	0.071	0.126

周期为p²的q元序列的k–错线性复杂度

k-error linear complexity of q-ary sequence of period p²

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 2

参考文献 23

相关文章 10

Metrics

推荐阅读 0

[1]	王艳,李顺波,薛改娜. SLCE序列的2-adic复杂度[J]. 通信学报, 2019, 40(8): 151-156.
[2]	游伟,戚文峰. 单圈T-函数的2-adic复杂度和1-错2-adic复杂度[J]. 通信学报, 2014, 35(3): 135-139.
[3]	游伟1，戚文峰2,3. 单圈T-函数的2-adic复杂度和1-错2-adic复杂度[J]. 通信学报, 2014, 35(3): 15-139.
[4]	高海英,金晨辉. 基于多个独立区分特征的序列密码最优联合区分器[J]. 通信学报, 2012, 33(7): 44-48.
[5]	谭刚敏,曾光,韩文报,张娜. 本原σ-LFSR序列距离向量的计算[J]. 通信学报, 2011, 32(9): 33-37.
[6]	杨阳,曾光. 序列密码算法RAKAPOSHI的动态移存器构造[J]. 通信学报, 2011, 32(11A): 178-183.
[7]	李鹤龄,戚文峰. F_p上pⁿ-周期序列的k-错误序列[J]. 通信学报, 2010, 31(6): 19-24.
[8]	谭林,戚文峰. 2^p周期二元序列的线性复杂度和k错线性复杂度[J]. 通信学报, 2008, 29(7): 44-49.
[9]	罗永龙,戚文峰. Klimov-Shamir T-函数的代数结构[J]. 通信学报, 2008, 29(10): 143-148.
[10]	刘训寿,戚文峰. 给定线性复杂度谱的序列的条数[J]. 通信学报, 2006, 27(12): 10-13.