# American Institute of Mathematical Sciences

August 2018, 12(3): 525-539. doi: 10.3934/amc.2018031

## On the linear complexities of two classes of quaternary sequences of even length with optimal autocorrelation

 1 Fujian Provincial Key Laboratory of Network Security and Cryptology, College of Mathematics and Informatics, Fujian Normal University, Fuzhou, Fujian 350117, China 2 School of Mathematics, Putian University, Putian, Fujian 351100, China

* Corresponding author: Pinhui Ke

Received  June 2017 Revised  January 2018 Published  July 2018

Fund Project: The authors are supported by National Natural Science Foundation of China (No. 61772292, 61772476), Natural Science Foundation of Fujian Province (No. 2015J01237), Fujian Normal University Innovative Research Team (No. IRTL1207)

Let $q$ be a prime greater than 4. In this paper, we determine the coefficients of the discrete Fourier transform over the finite field $\mathbb {F}_q$ of two classes of quaternary sequences of even length with optimal autocorrelation. They are quaternary sequence with period $2p$ derived from binary Legendre sequences and quaternary sequence with period $2p(p+2)$ derived from twin-prime sequences pair. As applications, the linear complexities over the finite field $\mathbb {F}_q$ of both of the quaternary sequences are determined.

Citation: 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
##### References:
 [1] M. Antweiler and L. Bomer, Complex sequences over ${\rm{G}}F(q)$ with a two-level autocorrelation function and a large linear span, IEEE Transaction on Information Theory, 38 (1992), 120-130. doi: 10.1109/18.108256. [2] D. Calabro and J. K. Wolf, On the synthesis of two-dimensional arrays with desirable correlation properties, Inform. Contro, 11 (1967), 537-560. doi: 10.1016/S0019-9958(67)90755-3. [3] Z. X. Chen and V. Edemskiy, Linear complexity of quaternary sequences over $Z_4$ derived from generalized cyclotomic classes modulo $2p$, International Journal of Netword Security, 19 (2017), 613-620. [4] Z. X. Chen, Linear complexity and trace representation of quaternary sequences over $\mathbb{Z}_4$ based on generalized cyclotomic classes modulo $pq$, Cryptography and Communications-discrete Structures, Boolean Functions and Sequences, 9 (2017), 445-458. doi: 10.1007/s12095-016-0185-6. [5] C. Ding, T. Helleseth and W. Shan, On the linear complexity of Legendre sequences, IEEE Transaction on Information Theory, 44 (1998), 1276-1278. doi: 10.1109/18.669398. [6] C. Ding, Codes from difference sets, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2015. [7] X. N. Du and Z. X. Chen, Linear complexity of quaternary sequence generated using generalized cyclomic classes modulo $2p$, IEICE Transactions on Fundamentals, 94 (2011), 1214-1217. [8] V. Edemskiy and A. Ivanov, The linear complexity of balanced quaternary sequences with optimal autocorrelation value, Cryptography and Communications, 7 (2015), 485-496. doi: 10.1007/s12095-015-0130-0. [9] S. W. Golomb and G. Gong, Signal Design for Good Correlation: For Wireless Communivation, in Cryptography and Radar Cambridge University Press, Cambridge, 2005. doi: 10.1017/CBO9780511546907. [10] D. H. Green and L. P. Garcia Perera, The linear complexity of related prime sequences, Proc. R. Soc. Lond. A, 460 (2004), 487-498. doi: 10.1098/rspa.2003.1216. [11] A. Johansen, T. Helleseth and X. Tang, The correlation disbution of quaternary sequences of period $2(2^n-1)$, IEEE Transaction on Information Theory, 54 (2008), 3130-3139. doi: 10.1109/TIT.2008.924727. [12] P. H. Ke and S. Y. Zhang, New classes of quaternary cyclotomic sequences of length $2p^m$ with high linear complexity, Information Processing Letters, 112 (2012), 646-650. doi: 10.1016/j.ipl.2012.05.011. [13] Y.-S. Kim, J.-W. Jang, S.-H. Kim and J.-S. No, New quaternary sequences with ideal autocorrelation constructed from legendre sequences, IEICE Transactions on Fundamentals, E96-A (2013), 1872-1882. [14] Y.-S. Kim, J.-W. Jang, S.-H. Kim and J.-S. No, New quaternary sequences with optimal autocorrelation, IEEE International Symposium on Information Theory, (2009), 286-289. [15] A. Klapper, The vulnerability of geometric sequences based on fields of odd characteristic, Journal of Cryptology, 7 (1994), 33-51. doi: 10.1007/BF00195208. [16] R. Marzouk and A. Winterhof, On the pseudorandomness of binary and quaternary sequences linked by the Gray mapping, Periodica Mathematica Hungarica, 60 (2010), 1-11. doi: 10.1007/s10998-010-1013-y. [17] J. L. Masseey, Shift register synthesis and BCH decoding, IEEE Transaction on Information Theory, 15 (1969), 122-127. [18] A. J. Menezes, P. C. Oorscgot and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press Series on Discrete Mathematics and its Applications. CRC Press, Boca Raton, FL, 1997. [19] R. A. Rueppe, The Science of Information Integrity, in Stream ciphers, In: Simmons G. J. (ed.) Contemporary Cryptology, IEEE Press, New York, (1992), 65–134. [20] M. Su and A. Winterhof, On the pseudorandomness of quaternary sequences derived from sequences over $F_4$, Periodica Mathematica Hungarica, 74 (2017), 79-87. doi: 10.1007/s10998-016-0143-2. [21] W. Su, Y. Yang, Z. C. Zhou and X. H. Tang, New quaternary sequence of even length with optimal autocorrelation, Science China in Information Sciences, 61 (2018), 022308, 13pp. doi: 10.1007/s11432-016-9087-2. [22] X. H. Tang and C. Ding, New classes of balanced quaternary and almost balanced binary sequences with optimal autocorrelation value, IEEE Transaction on Information Theory, 56 (2010), 6398-6405. doi: 10.1109/TIT.2010.2081170. [23] X. H. Tang and J. Linder, Almost quaternary sequences with ideal autocorrelation property, IEEE Signal Process Letters, 16 (2009), 38-40. [24] X. Tang and P. Udaya, A note on the optimal quadriphase sequences families, IEEE Transaction on Information Theory, 53 (2007), 433-436. doi: 10.1109/TIT.2006.887502. [25] R. J. Turyn, The linear complexity of the Legendre sequence, J. Soc. Ind. Appl. Math., 12 (1964), 115-116. doi: 10.1137/0112010. [26] P. Udaya and M. U. Siddiqi, Generalized GMW quadriphase sequences satisfying the Welch bound with equality, Applicable Algebra in Engineering, Communication and Computing, 10 (2000), 203-225. doi: 10.1007/s002000050125. [27] Q. Wang, Y. Jiang and D. Lin, Linear complexity of binary generalized cyclotomic sequences over ${\rm{G}}F(q)$, Journal of Complexity, 31 (2015), 731-740. doi: 10.1016/j.jco.2015.01.001. [28] Y. Yang and X. H. Tang, Balanced quaternary sequences pairs of odd period with(almost) optimal autocorrelation and cross-correlation, IEEE Communications Letters, 18 (2014), 1327-1330. doi: 10.1109/LCOMM.2014.2328603. [29] Z. Yang and P. H. Ke, Construction of quaternary sequences of length $p$ with low autocorrelation, Cryptography and Communications-discrete Structures, Boolean Functions and Sequences, 3 (2011), 55-64. doi: 10.1007/s12095-010-0034-y.

show all references

##### References:
 [1] M. Antweiler and L. Bomer, Complex sequences over ${\rm{G}}F(q)$ with a two-level autocorrelation function and a large linear span, IEEE Transaction on Information Theory, 38 (1992), 120-130. doi: 10.1109/18.108256. [2] D. Calabro and J. K. Wolf, On the synthesis of two-dimensional arrays with desirable correlation properties, Inform. Contro, 11 (1967), 537-560. doi: 10.1016/S0019-9958(67)90755-3. [3] Z. X. Chen and V. Edemskiy, Linear complexity of quaternary sequences over $Z_4$ derived from generalized cyclotomic classes modulo $2p$, International Journal of Netword Security, 19 (2017), 613-620. [4] Z. X. Chen, Linear complexity and trace representation of quaternary sequences over $\mathbb{Z}_4$ based on generalized cyclotomic classes modulo $pq$, Cryptography and Communications-discrete Structures, Boolean Functions and Sequences, 9 (2017), 445-458. doi: 10.1007/s12095-016-0185-6. [5] C. Ding, T. Helleseth and W. Shan, On the linear complexity of Legendre sequences, IEEE Transaction on Information Theory, 44 (1998), 1276-1278. doi: 10.1109/18.669398. [6] C. Ding, Codes from difference sets, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2015. [7] X. N. Du and Z. X. Chen, Linear complexity of quaternary sequence generated using generalized cyclomic classes modulo $2p$, IEICE Transactions on Fundamentals, 94 (2011), 1214-1217. [8] V. Edemskiy and A. Ivanov, The linear complexity of balanced quaternary sequences with optimal autocorrelation value, Cryptography and Communications, 7 (2015), 485-496. doi: 10.1007/s12095-015-0130-0. [9] S. W. Golomb and G. Gong, Signal Design for Good Correlation: For Wireless Communivation, in Cryptography and Radar Cambridge University Press, Cambridge, 2005. doi: 10.1017/CBO9780511546907. [10] D. H. Green and L. P. Garcia Perera, The linear complexity of related prime sequences, Proc. R. Soc. Lond. A, 460 (2004), 487-498. doi: 10.1098/rspa.2003.1216. [11] A. Johansen, T. Helleseth and X. Tang, The correlation disbution of quaternary sequences of period $2(2^n-1)$, IEEE Transaction on Information Theory, 54 (2008), 3130-3139. doi: 10.1109/TIT.2008.924727. [12] P. H. Ke and S. Y. Zhang, New classes of quaternary cyclotomic sequences of length $2p^m$ with high linear complexity, Information Processing Letters, 112 (2012), 646-650. doi: 10.1016/j.ipl.2012.05.011. [13] Y.-S. Kim, J.-W. Jang, S.-H. Kim and J.-S. No, New quaternary sequences with ideal autocorrelation constructed from legendre sequences, IEICE Transactions on Fundamentals, E96-A (2013), 1872-1882. [14] Y.-S. Kim, J.-W. Jang, S.-H. Kim and J.-S. No, New quaternary sequences with optimal autocorrelation, IEEE International Symposium on Information Theory, (2009), 286-289. [15] A. Klapper, The vulnerability of geometric sequences based on fields of odd characteristic, Journal of Cryptology, 7 (1994), 33-51. doi: 10.1007/BF00195208. [16] R. Marzouk and A. Winterhof, On the pseudorandomness of binary and quaternary sequences linked by the Gray mapping, Periodica Mathematica Hungarica, 60 (2010), 1-11. doi: 10.1007/s10998-010-1013-y. [17] J. L. Masseey, Shift register synthesis and BCH decoding, IEEE Transaction on Information Theory, 15 (1969), 122-127. [18] A. J. Menezes, P. C. Oorscgot and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press Series on Discrete Mathematics and its Applications. CRC Press, Boca Raton, FL, 1997. [19] R. A. Rueppe, The Science of Information Integrity, in Stream ciphers, In: Simmons G. J. (ed.) Contemporary Cryptology, IEEE Press, New York, (1992), 65–134. [20] M. Su and A. Winterhof, On the pseudorandomness of quaternary sequences derived from sequences over $F_4$, Periodica Mathematica Hungarica, 74 (2017), 79-87. doi: 10.1007/s10998-016-0143-2. [21] W. Su, Y. Yang, Z. C. Zhou and X. H. Tang, New quaternary sequence of even length with optimal autocorrelation, Science China in Information Sciences, 61 (2018), 022308, 13pp. doi: 10.1007/s11432-016-9087-2. [22] X. H. Tang and C. Ding, New classes of balanced quaternary and almost balanced binary sequences with optimal autocorrelation value, IEEE Transaction on Information Theory, 56 (2010), 6398-6405. doi: 10.1109/TIT.2010.2081170. [23] X. H. Tang and J. Linder, Almost quaternary sequences with ideal autocorrelation property, IEEE Signal Process Letters, 16 (2009), 38-40. [24] X. Tang and P. Udaya, A note on the optimal quadriphase sequences families, IEEE Transaction on Information Theory, 53 (2007), 433-436. doi: 10.1109/TIT.2006.887502. [25] R. J. Turyn, The linear complexity of the Legendre sequence, J. Soc. Ind. Appl. Math., 12 (1964), 115-116. doi: 10.1137/0112010. [26] P. Udaya and M. U. Siddiqi, Generalized GMW quadriphase sequences satisfying the Welch bound with equality, Applicable Algebra in Engineering, Communication and Computing, 10 (2000), 203-225. doi: 10.1007/s002000050125. [27] Q. Wang, Y. Jiang and D. Lin, Linear complexity of binary generalized cyclotomic sequences over ${\rm{G}}F(q)$, Journal of Complexity, 31 (2015), 731-740. doi: 10.1016/j.jco.2015.01.001. [28] Y. Yang and X. H. Tang, Balanced quaternary sequences pairs of odd period with(almost) optimal autocorrelation and cross-correlation, IEEE Communications Letters, 18 (2014), 1327-1330. doi: 10.1109/LCOMM.2014.2328603. [29] Z. Yang and P. H. Ke, Construction of quaternary sequences of length $p$ with low autocorrelation, Cryptography and Communications-discrete Structures, Boolean Functions and Sequences, 3 (2011), 55-64. doi: 10.1007/s12095-010-0034-y.
 [1] Nian Li, Xiaohu Tang, Tor Helleseth. A class of quaternary sequences with low correlation. Advances in Mathematics of Communications, 2015, 9 (2) : 199-210. doi: 10.3934/amc.2015.9.199 [2] Santos González, Llorenç Huguet, Consuelo Martínez, Hugo Villafañe. Discrete logarithm like problems and linear recurring sequences. Advances in Mathematics of Communications, 2013, 7 (2) : 187-195. doi: 10.3934/amc.2013.7.187 [3] Nam Yul Yu. A Fourier transform approach for improving the Levenshtein's lower bound on aperiodic correlation of binary sequences. Advances in Mathematics of Communications, 2014, 8 (2) : 209-222. doi: 10.3934/amc.2014.8.209 [4] Liqin Hu, Qin Yue, Fengmei Liu. Linear complexity of cyclotomic sequences of order six and BCH codes over GF(3). Advances in Mathematics of Communications, 2014, 8 (3) : 297-312. doi: 10.3934/amc.2014.8.297 [5] 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 [6] 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 [7] Jiarong Peng, Xiangyong Zeng, Zhimin Sun. Finite length sequences with large nonlinear complexity. Advances in Mathematics of Communications, 2018, 12 (1) : 215-230. doi: 10.3934/amc.2018015 [8] Yang Yang, Guang Gong, Xiaohu Tang. On $\omega$-cyclic-conjugated-perfect quaternary GDJ sequences. Advances in Mathematics of Communications, 2016, 10 (2) : 321-331. doi: 10.3934/amc.2016008 [9] 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 [10] Tongjiang Yan, Yanyan Liu, Yuhua Sun. Cyclic codes from two-prime generalized cyclotomic sequences of order 6. Advances in Mathematics of Communications, 2016, 10 (4) : 707-723. doi: 10.3934/amc.2016036 [11] 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 [12] E. Camouzis, H. Kollias, I. Leventides. Stable manifold market sequences. Journal of Dynamics & Games, 2018, 5 (2) : 165-185. doi: 10.3934/jdg.2018010 [13] Frank Fiedler. Small Golay sequences. Advances in Mathematics of Communications, 2013, 7 (4) : 379-407. doi: 10.3934/amc.2013.7.379 [14] Prof. Dr.rer.nat Widodo. Topological entropy of shift function on the sequences space induced by expanding piecewise linear transformations. Discrete & Continuous Dynamical Systems - A, 2002, 8 (1) : 191-208. doi: 10.3934/dcds.2002.8.191 [15] Hua Liang, Jinquan Luo, Yuansheng Tang. On cross-correlation of a binary $m$-sequence of period $2^{2k}-1$ and its decimated sequences by $(2^{lk}+1)/(2^l+1)$. Advances in Mathematics of Communications, 2017, 11 (4) : 693-703. doi: 10.3934/amc.2017050 [16] Anna Gierzkiewicz, Klaudiusz Wójcik. Lefschetz sequences and detecting periodic points. Discrete & Continuous Dynamical Systems - A, 2012, 32 (1) : 81-100. doi: 10.3934/dcds.2012.32.81 [17] A. Gasull, Víctor Mañosa, Xavier Xarles. Rational periodic sequences for the Lyness recurrence. Discrete & Continuous Dynamical Systems - A, 2012, 32 (2) : 587-604. doi: 10.3934/dcds.2012.32.587 [18] Lori Alvin. Toeplitz kneading sequences and adding machines. Discrete & Continuous Dynamical Systems - A, 2013, 33 (8) : 3277-3287. doi: 10.3934/dcds.2013.33.3277 [19] Ji-Woong Jang, Young-Sik Kim, Sang-Hyo Kim, Dae-Woon Lim. New construction methods of quaternary periodic complementary sequence sets. Advances in Mathematics of Communications, 2010, 4 (1) : 61-68. doi: 10.3934/amc.2010.4.61 [20] Georgi Grahovski, Rossen Ivanov. Generalised Fourier transform and perturbations to soliton equations. Discrete & Continuous Dynamical Systems - B, 2009, 12 (3) : 579-595. doi: 10.3934/dcdsb.2009.12.579

2017 Impact Factor: 0.564