American Institute of Mathematical Sciences

Advanced
doi: 10.3934/amc.2021019

On the linear complexity and autocorrelation of generalized cyclotomic binary sequences with period $ 4p^n $

Lin Yi , Xiangyong Zeng , , Zhimin Sun and  Shasha Zhang

Hubei Key Laboratory of Applied Mathematics, Faculty of Mathematics and Statistics, Hubei University, Wuhan 430062, China

* Corresponding author: Xiangyong Zeng

Received  January 2021 Revised  April 2021 Published  June 2021

Fund Project: The work was supported by Application foundation frontier project of Wuhan Science and Technology Bureau under Grant 2020010601012189, and by the National Nature Science Foundation of China (NSFC) under Grant 62072161. The work of Sun was supported by the Natural Science Foundation of Hubei under Grant 2019CFB544. The work of Zhang was supported by the Research Foundation of Education Bureau of Hubei Province, China under Grant D2020104

In this paper, a new class of generalized cyclotomic binary sequences with period $ 4p^n $ is proposed. These sequences are almost balanced, and the explicit formulas of their linear complexity and autocorrelation are presented.

Keywords: Binary sequence, generalized cyclotomy, linear complexity, autocorrelation, almost balanced.
Mathematics Subject Classification: Primary: 94A55; Secondary: 94A60.
Citation: Lin Yi, Xiangyong Zeng, Zhimin Sun, Shasha Zhang. On the linear complexity and autocorrelation of generalized cyclotomic binary sequences with period $ 4p^n $. Advances in Mathematics of Communications, doi: 10.3934/amc.2021019
References:
[1]

E. Bai, X. Liu and G. Xiao, Linear complexity of new generalized cyclotomic sequences of order two of length $pq$, IEEE Trans. Inf. Theory, 51 (2005), 1849-1853.  doi: 10.1109/TIT.2005.846450.  Google Scholar

[2]

D.M. Burton, Elementary Number Theory, McGram-Hill, New York, 1998.  Google Scholar

[3]

T. W. Cusick, C. Ding and A. Renvall, Stream Ciphers and Number Theory, Elsevier Science B. V., Amsterdam, 2004.  Google Scholar

[4]

C. Ding, Linear complexity of generalized cyclotomic binary sequences of order $2$, Finite Fields Appl., 3 (1997), 159-174.  doi: 10.1006/ffta.1997.0181.  Google Scholar

[5]

C. Ding, Autocorrelation values of generalized cyclotomic sequences of order two, IEEE Trans. Inf. Theory, 44 (1998), 1699-1702.  doi: 10.1109/18.681354.  Google Scholar

[6]

C. Ding and T. Helleseth, New generalized cyclotomy and its applications, Finite Fields Appl., 4 (1998), 140-166.  doi: 10.1006/ffta.1998.0207.  Google Scholar

[7]

C. Ding and T. Helleseth, Generalized cyclotomy codes of length $p^{m_{1}}_{1}p^{m_{2}}_{2}\cdots p^{m_{t}}_{t}$, IEEE Trans. Inf. Theory, 45 (1999), 467-474.  doi: 10.1109/18.748996.  Google Scholar

[8]

X. Dong, Linear complexity of generalized cyclotomic binary sequences of length $4p^n$, Inf. Sci. Lett., 4 (2015), 67-70.   Google Scholar

[9]

V. Edemskiy, About computation of the linear complexity of generalized cyclotomic sequences with period $p^{n+1}$, Des. Codes Cryptogr., 61 (2011), 251-260.  doi: 10.1007/s10623-010-9474-9.  Google Scholar

[10]

V. Edemskiy and O. Antonova, The evaluation of the linear complexity and the autocorrelation of generalized cyclotomic binary sequences of length $2^np^m$, International Journal of Mathematical Models and Methods in Applied Sciences, 9 (2015), 512-517.   Google Scholar

[11]

V. Edemskiy, C. Li, X. Zeng and T. Helleseth, The linear complexity of generalized cyclotomic binary sequences of period $p^n$, Des. Codes Cryptogr., 87 (2018), 1183-1197.  doi: 10.1007/s10623-018-0513-2.  Google Scholar

[12]

V. Edemskiy and C. Wu, On the linear complexity of binary sequences derived from generalized cyclotomic classes modulo $2^np^m$, WSEAS Transactions on Mathematics, 18 (2019), 197-202.   Google Scholar

[13]

C. Fan and G. Ge, A unified approach to Whiteman's and Ding-Helleseth's generalized cyclotomy over residue class rings, IEEE Trans. Inf. Theory, 60 (2014), 1326-1336.  doi: 10.1109/TIT.2013.2290694.  Google Scholar

[14] S. W. Golomb and G. Gong, Signal Design for Good Correlation, for Wireless Communications, Cryptography and Radar Applications, Cambridge University Press, Cambridge, 2005.  doi: 10.1017/CBO9780511546907.  Google Scholar
[15]

P. Ke, J. Zhang and S. Zhang, On the linear complexity and the autocorrelation of generalized cyclotomic binary sequences of length $2p^n$, Des. Codes Cryptogr., 67 (2013), 325-339.  doi: 10.1007/s10623-012-9610-9.  Google Scholar

[16]

Y. J. Kim, S. Y. Jin and H. Y. Song, Linear complexity and autocorrelation of prime cube sequences, AAECC, LNCS, 4851 (2007), 188-197.  doi: 10.1007/978-3-540-77224-8_23.  Google Scholar

[17]

J. L. Massey, Shift-register synthesis and BCH decoding, IEEE Trans. Inf. Theory, 15 (1969), 122-127.  doi: 10.1109/tit.1969.1054260.  Google Scholar

[18]

M. B. Nathnson, Elementary Methods in Number Theory, Springer, Berlin, GTM 195, 2003.  Google Scholar

[19]

A. L. Whiteman, A family of difference sets, Illinois J. Math., 6 (1962), 107-121.   Google Scholar

[20]

Z. Xiao, X. Zeng, C. Li and T. Helleseth, New generalized cyclotomic binary sequences of period $p^2$, Des. Codes Cryptogr., 86 (2018), 1483-1497.  doi: 10.1007/s10623-017-0408-7.  Google Scholar

[21]

T. Yan, B. Huang and G. Xiao, Cryptographic properties of some binary generalized cyclotomic sequences with length $p^2$, Inf. Sci., 178 (2008), 1078-1086.  doi: 10.1016/j.ins.2007.02.040.  Google Scholar

[22]

T. Yan, S. Li and G. Xiao, On the linear complexity of generalized cyclotomic sequences with period $p^m$, Appl. Math. Lett., 21 (2008), 187-193.  doi: 10.1016/j.aml.2007.03.011.  Google Scholar

[23]

T. Yan and X. Li, Some notes on the generalized cyclotomic binary sequences of length $2p^m$ and $p^m$, IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, 96 (2013), 2049-2051.  doi: 10.1007/s00200-012-0177-5.  Google Scholar

[24]

T. Yan, R. Sun and G. Xiao, Autocorrelation and linear complexity of the new generalized cyclotomic sequences, IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, 90 (2007), 857-864.   Google Scholar

[25]

X. Zeng, H. Cai, X. Tang and Y. Yang, Optimal frequency hopping sequences of odd length, IEEE Trans. Inf. Theory, 59 (2013), 3237-3248.  doi: 10.1109/TIT.2013.2237754.  Google Scholar

[26]

J. Zhang, C. Zhao and X. Ma, Linear complexity of generalized cyclotomic binary sequences of length $2p^m$, Applicable Algebra in Engineering Communication and Computing, 21 (2010), 93-108.  doi: 10.1007/s00200-009-0116-2.  Google Scholar

show all references

References:
[1]

E. Bai, X. Liu and G. Xiao, Linear complexity of new generalized cyclotomic sequences of order two of length $pq$, IEEE Trans. Inf. Theory, 51 (2005), 1849-1853.  doi: 10.1109/TIT.2005.846450.  Google Scholar

[2]

D.M. Burton, Elementary Number Theory, McGram-Hill, New York, 1998.  Google Scholar

[3]

T. W. Cusick, C. Ding and A. Renvall, Stream Ciphers and Number Theory, Elsevier Science B. V., Amsterdam, 2004.  Google Scholar

[4]

C. Ding, Linear complexity of generalized cyclotomic binary sequences of order $2$, Finite Fields Appl., 3 (1997), 159-174.  doi: 10.1006/ffta.1997.0181.  Google Scholar

[5]

C. Ding, Autocorrelation values of generalized cyclotomic sequences of order two, IEEE Trans. Inf. Theory, 44 (1998), 1699-1702.  doi: 10.1109/18.681354.  Google Scholar

[6]

C. Ding and T. Helleseth, New generalized cyclotomy and its applications, Finite Fields Appl., 4 (1998), 140-166.  doi: 10.1006/ffta.1998.0207.  Google Scholar

[7]

C. Ding and T. Helleseth, Generalized cyclotomy codes of length $p^{m_{1}}_{1}p^{m_{2}}_{2}\cdots p^{m_{t}}_{t}$, IEEE Trans. Inf. Theory, 45 (1999), 467-474.  doi: 10.1109/18.748996.  Google Scholar

[8]

X. Dong, Linear complexity of generalized cyclotomic binary sequences of length $4p^n$, Inf. Sci. Lett., 4 (2015), 67-70.   Google Scholar

[9]

V. Edemskiy, About computation of the linear complexity of generalized cyclotomic sequences with period $p^{n+1}$, Des. Codes Cryptogr., 61 (2011), 251-260.  doi: 10.1007/s10623-010-9474-9.  Google Scholar

[10]

V. Edemskiy and O. Antonova, The evaluation of the linear complexity and the autocorrelation of generalized cyclotomic binary sequences of length $2^np^m$, International Journal of Mathematical Models and Methods in Applied Sciences, 9 (2015), 512-517.   Google Scholar

[11]

V. Edemskiy, C. Li, X. Zeng and T. Helleseth, The linear complexity of generalized cyclotomic binary sequences of period $p^n$, Des. Codes Cryptogr., 87 (2018), 1183-1197.  doi: 10.1007/s10623-018-0513-2.  Google Scholar

[12]

V. Edemskiy and C. Wu, On the linear complexity of binary sequences derived from generalized cyclotomic classes modulo $2^np^m$, WSEAS Transactions on Mathematics, 18 (2019), 197-202.   Google Scholar

[13]

C. Fan and G. Ge, A unified approach to Whiteman's and Ding-Helleseth's generalized cyclotomy over residue class rings, IEEE Trans. Inf. Theory, 60 (2014), 1326-1336.  doi: 10.1109/TIT.2013.2290694.  Google Scholar

[14] S. W. Golomb and G. Gong, Signal Design for Good Correlation, for Wireless Communications, Cryptography and Radar Applications, Cambridge University Press, Cambridge, 2005.  doi: 10.1017/CBO9780511546907.  Google Scholar
[15]

P. Ke, J. Zhang and S. Zhang, On the linear complexity and the autocorrelation of generalized cyclotomic binary sequences of length $2p^n$, Des. Codes Cryptogr., 67 (2013), 325-339.  doi: 10.1007/s10623-012-9610-9.  Google Scholar

[16]

Y. J. Kim, S. Y. Jin and H. Y. Song, Linear complexity and autocorrelation of prime cube sequences, AAECC, LNCS, 4851 (2007), 188-197.  doi: 10.1007/978-3-540-77224-8_23.  Google Scholar

[17]

J. L. Massey, Shift-register synthesis and BCH decoding, IEEE Trans. Inf. Theory, 15 (1969), 122-127.  doi: 10.1109/tit.1969.1054260.  Google Scholar

[18]

M. B. Nathnson, Elementary Methods in Number Theory, Springer, Berlin, GTM 195, 2003.  Google Scholar

[19]

A. L. Whiteman, A family of difference sets, Illinois J. Math., 6 (1962), 107-121.   Google Scholar

[20]

Z. Xiao, X. Zeng, C. Li and T. Helleseth, New generalized cyclotomic binary sequences of period $p^2$, Des. Codes Cryptogr., 86 (2018), 1483-1497.  doi: 10.1007/s10623-017-0408-7.  Google Scholar

[21]

T. Yan, B. Huang and G. Xiao, Cryptographic properties of some binary generalized cyclotomic sequences with length $p^2$, Inf. Sci., 178 (2008), 1078-1086.  doi: 10.1016/j.ins.2007.02.040.  Google Scholar

[22]

T. Yan, S. Li and G. Xiao, On the linear complexity of generalized cyclotomic sequences with period $p^m$, Appl. Math. Lett., 21 (2008), 187-193.  doi: 10.1016/j.aml.2007.03.011.  Google Scholar

[23]

T. Yan and X. Li, Some notes on the generalized cyclotomic binary sequences of length $2p^m$ and $p^m$, IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, 96 (2013), 2049-2051.  doi: 10.1007/s00200-012-0177-5.  Google Scholar

[24]

T. Yan, R. Sun and G. Xiao, Autocorrelation and linear complexity of the new generalized cyclotomic sequences, IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, 90 (2007), 857-864.   Google Scholar

[25]

X. Zeng, H. Cai, X. Tang and Y. Yang, Optimal frequency hopping sequences of odd length, IEEE Trans. Inf. Theory, 59 (2013), 3237-3248.  doi: 10.1109/TIT.2013.2237754.  Google Scholar

[26]

J. Zhang, C. Zhao and X. Ma, Linear complexity of generalized cyclotomic binary sequences of length $2p^m$, Applicable Algebra in Engineering Communication and Computing, 21 (2010), 93-108.  doi: 10.1007/s00200-009-0116-2.  Google Scholar

Table 1.  The autocorrelation distribution of the binary sequence of period $ 108 $
$ R_{S^{(d,e)}}(\tau) $ $ \tau $
$ -68 $ $ 1, 11, 13, 23, 25, 35, 37, 47, 49, 59, 61, 71, 73, 83, 85, 95, 97,107 $
$ 32 $ $ 2, 10, 14, 22, 26, 34, 38, 46, 50, 58, 62, 70, 74, 82, 86, 94, 98,106 $
$ -4 $ $ 3, 9, 33, 39, 69, 75, 99,105 $
$ -32 $ $ 4, 8, 16, 20, 28, 32, 40, 44, 52, 56, 64, 68, 76, 80, 88, 92,100,104 $
$ 68 $ $ 5, 7, 17, 19, 29, 31, 41, 43, 53, 55, 65, 67, 77, 79, 89, 91,101,103 $
$ -80 $ $ 6, 30, 42, 66, 78,102 $
$ 80 $ $ 12, 24, 48, 60, 84, 96 $
$ 4 $ $ 15, 21, 45, 51, 57, 63, 87, 93,99 $
$ -96 $ $ 18, 90 $
$ 0 $ $ 27, 81 $
$ 96 $ $ 36, 72 $
$ -104 $ $ 54 $
Table Options

Download as excel

$ R_{S^{(d,e)}}(\tau) $ $ \tau $
$ -68 $ $ 1, 11, 13, 23, 25, 35, 37, 47, 49, 59, 61, 71, 73, 83, 85, 95, 97,107 $
$ 32 $ $ 2, 10, 14, 22, 26, 34, 38, 46, 50, 58, 62, 70, 74, 82, 86, 94, 98,106 $
$ -4 $ $ 3, 9, 33, 39, 69, 75, 99,105 $
$ -32 $ $ 4, 8, 16, 20, 28, 32, 40, 44, 52, 56, 64, 68, 76, 80, 88, 92,100,104 $
$ 68 $ $ 5, 7, 17, 19, 29, 31, 41, 43, 53, 55, 65, 67, 77, 79, 89, 91,101,103 $
$ -80 $ $ 6, 30, 42, 66, 78,102 $
$ 80 $ $ 12, 24, 48, 60, 84, 96 $
$ 4 $ $ 15, 21, 45, 51, 57, 63, 87, 93,99 $
$ -96 $ $ 18, 90 $
$ 0 $ $ 27, 81 $
$ 96 $ $ 36, 72 $
$ -104 $ $ 54 $
[1]

Richard Hofer, Arne Winterhof. On the arithmetic autocorrelation of the Legendre sequence. Advances in Mathematics of Communications, 2017, 11 (1) : 237-244. doi: 10.3934/amc.2017015
[2]

Alina Ostafe, Igor E. Shparlinski, Arne Winterhof. On the generalized joint linear complexity profile of a class of nonlinear pseudorandom multisequences. Advances in Mathematics of Communications, 2010, 4 (3) : 369-379. doi: 10.3934/amc.2010.4.369
[3]

Zhixiong Chen, Vladimir Edemskiy, Pinhui Ke, Chenhuang Wu. On $k$-error linear complexity of pseudorandom binary sequences derived from Euler quotients. Advances in Mathematics of Communications, 2018, 12 (4) : 805-816. doi: 10.3934/amc.2018047
[4]

Jianqin Zhou, Wanquan Liu, Xifeng Wang. Structure analysis on the k-error linear complexity for 2n-periodic binary sequences. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1743-1757. doi: 10.3934/jimo.2017016
[5]

Jianqin Zhou, Wanquan Liu, Xifeng Wang. Complete characterization of the first descent point distribution for the k-error linear complexity of 2n-periodic binary sequences. Advances in Mathematics of Communications, 2017, 11 (3) : 429-444. doi: 10.3934/amc.2017036
[6]

Jianqin Zhou, Wanquan Liu, Xifeng Wang, Guanglu Zhou. On the $ k $-error linear complexity for $ p^n $-periodic binary sequences via hypercube theory. Mathematical Foundations of Computing, 2019, 2 (4) : 279-297. doi: 10.3934/mfc.2019018
[7]

Kai-Uwe Schmidt, Jonathan Jedwab, Matthew G. Parker. Two binary sequence families with large merit factor. Advances in Mathematics of Communications, 2009, 3 (2) : 135-156. doi: 10.3934/amc.2009.3.135
[8]

Zilong Wang, Guang Gong. Correlation of binary sequence families derived from the multiplicative characters of finite fields. Advances in Mathematics of Communications, 2013, 7 (4) : 475-484. doi: 10.3934/amc.2013.7.475
[9]

Pinhui Ke, Yueqin Jiang, Zhixiong Chen. On the linear complexities of two classes of quaternary sequences of even length with optimal autocorrelation. Advances in Mathematics of Communications, 2018, 12 (3) : 525-539. doi: 10.3934/amc.2018031
[10]

Ji-Woong Jang, Young-Sik Kim, Sang-Hyo Kim. New design of quaternary LCZ and ZCZ sequence set from binary LCZ and ZCZ sequence set. Advances in Mathematics of Communications, 2009, 3 (2) : 115-124. doi: 10.3934/amc.2009.3.115
[11]

Yang Yang, Xiaohu Tang, Guang Gong. New almost perfect, odd perfect, and perfect sequences from difference balanced functions with d-form property. Advances in Mathematics of Communications, 2017, 11 (1) : 67-76. doi: 10.3934/amc.2017002
[12]

Xiaohui Liu, Jinhua Wang, Dianhua Wu. Two new classes of binary sequence pairs with three-level cross-correlation. Advances in Mathematics of Communications, 2015, 9 (1) : 117-128. doi: 10.3934/amc.2015.9.117
[13]

Huaning Liu, Xi Liu. On the correlation measures of orders $ 3 $ and $ 4 $ of binary sequence of period $ p^2 $ derived from Fermat quotients. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021008
[14]

Tomás Caraballo, David Cheban. Almost periodic and almost automorphic solutions of linear differential equations. Discrete & Continuous Dynamical Systems, 2013, 33 (5) : 1857-1882. doi: 10.3934/dcds.2013.33.1857
[15]

Tsonka Baicheva, Iliya Bouyukliev. On the least covering radius of binary linear codes of dimension 6. Advances in Mathematics of Communications, 2010, 4 (3) : 399-404. doi: 10.3934/amc.2010.4.399
[16]

Martin Redmann, Melina A. Freitag. Balanced model order reduction for linear random dynamical systems driven by Lévy noise. Journal of Computational Dynamics, 2018, 5 (1&2) : 33-59. doi: 10.3934/jcd.2018002
[17]

Laurent Gosse. Well-balanced schemes using elementary solutions for linear models of the Boltzmann equation in one space dimension. Kinetic & Related Models, 2012, 5 (2) : 283-323. doi: 10.3934/krm.2012.5.283
[18]

Yang Yang, Xiaohu Tang, Guang Gong. Even periodic and odd periodic complementary sequence pairs from generalized Boolean functions. Advances in Mathematics of Communications, 2013, 7 (2) : 113-125. doi: 10.3934/amc.2013.7.113
[19]

Álvaro Castañeda, Gonzalo Robledo. Almost reducibility of linear difference systems from a spectral point of view. Communications on Pure & Applied Analysis, 2017, 16 (6) : 1977-1988. doi: 10.3934/cpaa.2017097
[20]

Vittorino Pata. Exponential stability in linear viscoelasticity with almost flat memory kernels. Communications on Pure & Applied Analysis, 2010, 9 (3) : 721-730. doi: 10.3934/cpaa.2010.9.721

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (19)
  • HTML views (22)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences