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

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

Abstract

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

CLC Number:

TP309

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.

Figures/Tables 2

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

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

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 2

References 23

Related Articles 15

Metrics

Recommended 0

[1]	Zhaocun ZHOU, Dengguo FENG. Survey on approaches of stream cipher cryptanalysis [J]. Journal on Communications, 2022, 43(11): 183-198.
[2]	Yan WANG,Shunbo LI,Gaina XUE. 2-adic complexity of SLCE sequence [J]. Journal on Communications, 2019, 40(8): 151-156.
[3]	Zhixiong CHEN,Chenhuang WU. k-error linear complexity of binary cyclotomic generators [J]. Journal on Communications, 2019, 40(2): 197-206.
[4]	Ruilin LI,Jiao HU,Chaojing TANG. Collision analysis of the GMR-2 cipher used in the satellite phone [J]. Journal on Communications, 2018, 39(2): 88-95.
[5]	Long-fei LIU,Kai YANG,Xiao-yuan YANG. On the linear complexity of a new generalized cyclotomic sequence with length ^mover GF(h) [J]. Journal on Communications, 2017, 38(9): 39-45.
[6]	Meng MA,Ya-qun ZHAO. Research on linear approximations of simplified Trivium [J]. Journal on Communications, 2016, 37(6): 185-191.
[7]	. The 2-adic complexity and the 1-error 2-adic complexity of single cycle T-functions [J]. Journal on Communications, 2014, 35(3): 15-139.
[8]	Wei YOU,Wen-feng QI. The 2-adic complexity and the 1-error 2-adic complexity of single cycle T-functions [J]. Journal on Communications, 2014, 35(3): 135-139.
[9]	Hai-ying GAO,Chen-hui JIN. Optimal combined distinguisher of stream cipher with multiple independent distinguishing characters [J]. Journal on Communications, 2012, 33(7): 44-48.
[10]	Li-hua DONG,Yu-pu HU,Yong ZENG. Computing on the joint quadratic complexity of multiple periodic sequences [J]. Journal on Communications, 2012, 33(6): 11-18.
[11]	Gang-min TAN,Guang ZENG,Wen-bao HAN,Na ZHANG. Calculation of interval vectors of primitive σ-LFSR sequences [J]. Journal on Communications, 2011, 32(9): 33-37.
[12]	Yang YANG,Guang ZENG. Construction of dynamic linear feedback shift registers in RAKAPOSHI stream cipher [J]. Journal on Communications, 2011, 32(11A): 178-183.
[13]	Feng-rong ZHANG,Yu-pu HU,Hua MA,Min XIE,Jun-tao GAO. Recursive constructions and counting of orthomorphic permutations [J]. Journal on Communications, 2011, 32(11A): 204-208.
[14]	Jian-qin ZHOU,Xiao-ping DAI,Xiao-jun WANG. On the stable k-error linear complexity of periodic sequences [J]. Journal on Communications, 2011, 32(11A): 213-220.
[15]	Si-wei SUN,Lei HU. Two improved attacks on the WEP data encryption protocol [J]. Journal on Communications, 2010, 31(9): 103-109.