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

Pinhui Ke; Yueqin Jiang; Zhixiong Chen

doi:10.3934/amc.2018031

Previous Article
An asymmetric ZCZ sequence set with inter-subset uncorrelated property and flexible ZCZ length
AMC Home
This Issue
Next Article
A note on some algebraic trapdoors for block ciphers

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

Pinhui Ke ^1,, , Yueqin Jiang ^1, and Zhixiong Chen ^2,

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.

Keywords: Discrete Fourier transform, Legendre sequence, twin-prime sequences pair, linear complexity, quaternary sequences.

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

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]	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
[6]	Jianqin Zhou, Wanquan Liu, Xifeng Wang. Structure analysis on the k-error linear complexity for 2ⁿ-periodic binary sequences. Journal of Industrial and Management Optimization, 2017, 13 (4) : 1743-1757. doi: 10.3934/jimo.2017016
[7]	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, 2021 doi: 10.3934/amc.2021019
[8]	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
[9]	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
[10]	Büşra Özden, Oǧuz Yayla. Partial direct product difference sets and almost quaternary sequences. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021010
[11]	Jianqin Zhou, Wanquan Liu, Xifeng Wang. Complete characterization of the first descent point distribution for the k-error linear complexity of 2ⁿ-periodic binary sequences. Advances in Mathematics of Communications, 2017, 11 (3) : 429-444. doi: 10.3934/amc.2017036
[12]	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
[13]	Tian-Xiao He, Peter J.-S. Shiue, Zihan Nie, Minghao Chen. Recursive sequences and girard-waring identities with applications in sequence transformation. Electronic Research Archive, 2020, 28 (2) : 1049-1062. doi: 10.3934/era.2020057
[14]	Ferruh Özbudak, Eda Tekin. Correlation distribution of a sequence family generalizing some sequences of Trachtenberg. Advances in Mathematics of Communications, 2021, 15 (4) : 647-662. doi: 10.3934/amc.2020087
[15]	Pinhui Ke, Panpan Qiao, Yang Yang. On the equivalence of several classes of quaternary sequences with optimal autocorrelation and length $ 2p$. Advances in Mathematics of Communications, 2022, 16 (2) : 285-302. doi: 10.3934/amc.2020112
[16]	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
[17]	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
[18]	Tian-Xiao He, Peter J.-S. Shiue. Identities for linear recursive sequences of order $ 2 $. Electronic Research Archive, 2021, 29 (5) : 3489-3507. doi: 10.3934/era.2021049
[19]	Lin Yi, Xiangyong Zeng, Zhimin Sun. On finite length nonbinary sequences with large nonlinear complexity over the residue ring $ \mathbb{Z}_{m} $. Advances in Mathematics of Communications, 2021, 15 (4) : 701-720. doi: 10.3934/amc.2020091
[20]	E. Camouzis, H. Kollias, I. Leventides. Stable manifold market sequences. Journal of Dynamics and Games, 2018, 5 (2) : 165-185. doi: 10.3934/jdg.2018010

American Institute of Mathematical Sciences

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

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

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

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors