Linear complexity and autocorrelation of a new class of binary generalized cyclotomic sequences of order two and length pqr

doi:10.21629/JSEE.2019.04.03

Journal of Systems Engineering and Electronics ›› 2019, Vol. 30 ›› Issue (4): 651-661.doi: 10.21629/JSEE.2019.04.03

• Electronics Technology • Previous Articles Next Articles

Linear complexity and autocorrelation of a new class of binary generalized cyclotomic sequences of order two and length pqr

Wenjuan JIA¹(), Juntao GAO^2,*(), Peng ZHANG¹()

¹ School of Telecommunications Engineering, Xidian University, Xi'an 710071, China
² The State Key Laboratory of Integrated Services Network, Xidian University, Xi'an 710071, China

Received:2018-07-30 Online:2019-08-01 Published:2019-08-29
Contact: Juntao GAO E-mail:18368910175@163.com;jtgao@mail.xidian.edu.cn;297966738@qq.com
About author:JIA Wenjuan was born in 1994. She received her B.S. degree from Northwest Normal University. She is a Ph.D candidate in cryptography from Xidian University. Her research interests include Latticebased cryptography, stream cipher and pseudorandom sequence. E-mail:18368910175@163.com|GAO Juntao was born in 1979. He received his D.E.degree incryptography from Xidian University. He is now an associate professor. His research interests include block chain, stream cipher and pseudorandom sequence. E-mail:jtgao@mail.xidian.edu.cn|ZHANG Peng was born in 1992. He received his B.S. degree from Henan University and his M.S. degree in cryptography from Xidian University. His research interests include compressive sensing and cryptography. E-mail:297966738@qq.com
Supported by:
the National Key Research and Development Program of China(2016YFB0800601);the Natural Science Foundation of China(61303217);the Natural Science Foundation of China(61502372);the Fundamental Research Funds for the Central Universities(JB140115);the Natural Science Foundation of Shaanxi Province(2013JQ8002);the Natural Science Foundation of Shaanxi Province(2014JQ8313);This work was supported by the National Key Research and Development Program of China (2016YFB0800601), the Natural Science Foundation of China (61303217; 61502372), the Fundamental Research Funds for the Central Universities (JB140115), and the Natural Science Foundation of Shaanxi Province (2013JQ8002; 2014JQ8313)

Abstract

Abstract:

Cyclotomic sequences have good cryptographic properties and are closely related to difference sets. This paper proposes a new class of binary generalized cyclotomic sequences of order two and length pqr. Its linear complexity, minimal polynomial, and autocorrelation are investigated. The results show that these sequences have a large linear complexity when 2 ∈D₁, which means they can resist the Berlekamp-Massey attack. Furthermore, the autocorrelation values are close to 0 with a probability of approximately 1-1/r. Therefore, when r is a big prime, the new sequence has a good autocorrelation.

Key words: generalized cyclotomic sequence, linear complexity, minimal polynomial, autocorrelation value

Wenjuan JIA, Juntao GAO, Peng ZHANG. Linear complexity and autocorrelation of a new class of binary generalized cyclotomic sequences of order two and length pqr[J]. Journal of Systems Engineering and Electronics, 2019, 30(4): 651-661.

Figures/Tables 6

Table 1

Table 2

Table 3

Table 4

Fig 1

Fig 2

References 31

1	TURYN R J. The linear generation of the legendre sequence. Journal of the Society for Industrial and Applied Mathematics, 1964, 12 (1): 115- 116. doi: 10.1137/0112010
2	DING C, HESSESETH T, SHAN W. On the linear complexity of Legendre sequences. IEEE Trans. on Information Theory, 1998, 44 (3): 1276- 1278. doi: 10.1109/18.669398
3	STANTON R G, SPROTT D A. A family of difference sets. Canadian Journal of Mathematics, 1958, 6 (1): 73- 77.
4	DING C. Binary cyclotomic generators. Lecture Notes in Computer Science, 1994, 1008, 29- 60.
5	DING C. Linear complexity of generalized cyclotomic binary sequences of order 2. Finite Fields and Their Applications, 1997, 3 (2): 159- 174. doi: 10.1006/ffta.1997.0181
6	DING C. Autocorrelation values of generalized cyclotomic sequences of order two. IEEE Trans. on Information Theory, 1998, 44 (4): 1699- 1702. doi: 10.1109/18.681354
7	BAI E, FU X, XIAO G. On the linear complexity of generalized cyclotomic sequences of order four over Zpq. IEICE Trans. on Fundamentals, 2005, 88 (1): 392- 395.
8	BRANDSTÄTTER N, WINTERHOF A. Some notes of the two-prime generator of order 2. IEEE Trans. on Information Theory, 2005, 51 (10): 3654- 3657. doi: 10.1109/TIT.2005.855615
9	DING C, HELLESETH T. New generalized cyclotomy and its application. Finite Fields and Their Applications, 1998, 4 (2): 140- 166. doi: 10.1006/ffta.1998.0207
10	BAI E, LIU X. Generalized cyclotomic sequences of order four over Z pq and their autocorrelation values. Chinese Journal of Engineering Mathematics, 2008, 25 (5): 894- 900.
11	BAI E, LIU X, XIAO G. Lilnear complexity of new generelized cyclotomic sequences of order two of length pq. IEEE Trans. on Information Theory, 2005, 51 (5): 1849- 1853. doi: 10.1109/TIT.2005.846450
12	YAN T, HONG L, XIAO G. The linear complexity of new generalized cyclotomic binary sequences of order four. Information Sciences, 2008, 178 (3): 807- 815.
13	JIN S, KIM Y, SONG H. Autocorrelation of new generalized cyclotomic sequences of period pn. IEICE Trans. on Fundamentals, 2010, 93 (11): 2345- 2348.
14	KE P, ZHANG J, ZHANG S. On the linear complexity and the autocorrelation of generalized cyclotomic binary sequences of length 2pm. Designs, Codes and Cryptography, 2013, 67 (3): 325- 339. doi: 10.1007/s10623-012-9610-9
15	LI S, CHEN Z, SUN R, et al. On the randomness of generalized cyclotomic sequences of order two and length pq. IEICE Trans. on Fundamentals, 2007, 90 (9): 2037- 2041.
16	LI S, CHEN Z, FU X, et al. Autocorrelation values of new generalized cyclotomic sequences of order two and length pq. Journal of Computer Science and Technology, 2007, 22 (6): 830- 834. doi: 10.1007/s11390-007-9099-2
17	Meidl W. Remarks on a cyclotomic sequence. Designs, Codes and Cryptography, 2009, 51 (1): 33- 43.
18	YAN T, SUN R, XIAO G. Autocorrelation and linear complexity of the new generalized cyclotomic sequences. IEICE Trans. on Fundamentals, 2008, 90 (4): 857- 864.
19	YAN T, DU X, XIAO G, et al. Linear complexity of binary Whiteman generalized cyclotomic sequences of order 2k. Information Sciences, 2009, 179 (7): 1019- 1023. doi: 10.1016/j.ins.2008.11.006
20	YAN T, HUANG B, XIAO G. Cryptographic properties of some binary generalized cyclotomic sequences with the length p2. Information Sciences, 2008, 178 (4): 1078- 1086.
21	YAN T, LI S, XIAO G. On thelinear complexity of generalized cyclotomic sequences with the period pm. Appliced Mathematics Letters, 2008, 21 (2): 187- 193.
22	YAN T, CHEN Z, XIAO G. Linear complexity of Ding generalized cyclotomic sequences. Journal of Shanghai University, 2007, 11 (1): 22- 26. doi: 10.1007/s11741-007-0103-4
23	ZHANG J, ZHAO C, MA X. Linear complexity of generalized cyclotomoc binary sequences of length 2pm. Applicable Algebra in Engineering, Communication and Computing, 2010, 21 (2): 93- 108. doi: 10.1007/s00200-009-0116-2
24	CHEN Z, DU X, WU C. Pseodu-randomness of certain sequences of k symbols with length pq. Journal of Computer Science and Technology, 2011, 26 (2): 276- 282. doi: 10.1007/s11390-011-9434-5
25	CHEN Z, DU X. Linear complexity and auto-correlation values of a polyphase generalized cyclotomic sequence of length pq. Frontiers of Computer Science, 2010, 4 (4): 529- 535. doi: 10.1007/s11704-010-0329-3
26	DING C, HELLESETH T. On cyclotomic generator of order r. Information Processing Letters, 1998, 66 (1): 21- 25.
27	CHANG Z, ZHOU Y, KE P. Linear complexity of new generalized cyclotomic sequences of order two and length pqr. Acta Electronica Science, 2015, 43 (1): 166- 170.
28	LIU L, YANG X, DU X, et al. On the linear complexity of new generalized cyclotomic binary sequences of order two and period pqr. Tsinghua Science and Technology, 2016, 21 (3): 295- 301. doi: 10.1109/TST.2016.7488740
29	LYU C, XIAO G Z, YAN T J. On linear complexity of a new generalized cyclotmic sequence of order two over $\mathbb{Z}$_p₁p₂p₃. Journal of Computational Information Systems, 2015, 11 (17): 6355- 6362.
30	CUSICK T W, DING C, RENVALL A. Stream cipher and number theory. Amsterdam: North-Holland, 1988.
31	LIDL R, NIEDERREITER H. Finite fields. 2nd ed Cambridge: Cambridge University Press, 1997.

Sequence	Balance	$LC_{\max}$	$AC$
[27]	$\begin{array}{l} \| (p-1)(q+r-1) -qr+2\| \end{array}$	$pqr-(p-1)r-1$	$\times $
[28]	$\begin{array}{l} \| (p-1)(q+r-3)- (q-1)(r-1)-1\| \end{array}$	$pqr-(p-1)(q-1)-1$	$\times $
[29]	$\begin{array}{l} \| (p_1 -1)(p_2 +p_3 -1) -p_2 p_3 +2\| \end{array}$	$p_1 p_2 p_3 -p_1 $	$\times $
Ours	$\begin{array}{l} \| (p-1)(q+r-3) -qr+2\| \end{array}$	$pqr-(p-1)(r-1)-1$	$\surd $

$(p, q, r)$	$g$	$2\in D_1 $	$t$	$LC(s_i)$	Our results
(19, 11, 3)	2	Yes	627	590	590
(19, 11, 5)	2	Yes	1 045	792	792
(47, 31, 23)	11	No	33 511	17 318	17 318
(43, 31, 17)	3	No	22 661	10 648	10 648

(479, 383, 227)	$AC(s_i, \tau)$	Our results
$\tau \in P_1 $	0.000 263	0.000 263
$\tau \in P_2 $	0.994 766	0.994 766
$\tau \in P_3 $	–0.002 263	–0.002 263
$\tau \in Q_2 $	0.995 795	0.995 795
$\tau \in Q_3 $	–0.001 850	–0.001 850
$\tau \in R$	0.990 573	0.990 573
$\tau \in \mathbb{Z}_N^\ast $	–0.004 370	–0.004 370

(167, 83, 41)	$AC(s_i, \tau)$	Our results
$\tau \in P_1, \left({\dfrac{\tau }{r}} \right) = 1$	0.040 741	0.040 741
$\tau \in P_1, \left({\dfrac{\tau }{r}} \right) = -1$	-0.055 068	-0.055 068
$\tau \in P_2 $	0.975 457	0.975 457
$\tau \in P_3, \left({\dfrac{\tau }{r}} \right) = 1$	0.029 057	0.029 057
$\tau \in P_3, \left({\dfrac{\tau }{r}} \right) = -1$	-0.063 246	-0.063 246
$\tau \in Q_2 $	0.987 591	0.987 591
$\tau \in Q_3, \left({\dfrac{\tau }{r}} \right) = 1$	0.034 132	0.034 132
$\tau \in Q_3, \left({\dfrac{\tau }{r}} \right) = -1$	-0.061 100	-0.061 100
$\tau \in R$	0.963 217	0.963 217
$\tau \in D_0 $	0.022 518	0.022 518
$\tau \in D_1 $	-0.069 243	-0.069 243

Linear complexity and autocorrelation of a new class of binary generalized cyclotomic sequences of order two and length pqr

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 6

References 31

Related Articles 0

Recommended Articles

Metrics

Comments