American Institute of Mathematical Sciences

Advanced
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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[6]

C. Ding, Codes from difference sets, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2015.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

J. L. Masseey, Shift register synthesis and BCH decoding, IEEE Transaction on Information Theory, 15 (1969), 122-127.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[23]

X. H. Tang and J. Linder, Almost quaternary sequences with ideal autocorrelation property, IEEE Signal Process Letters, 16 (2009), 38-40.   Google Scholar

[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.  Google Scholar

[25]

R. J. Turyn, The linear complexity of the Legendre sequence, J. Soc. Ind. Appl. Math., 12 (1964), 115-116.  doi: 10.1137/0112010.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[6]

C. Ding, Codes from difference sets, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2015.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

J. L. Masseey, Shift register synthesis and BCH decoding, IEEE Transaction on Information Theory, 15 (1969), 122-127.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[23]

X. H. Tang and J. Linder, Almost quaternary sequences with ideal autocorrelation property, IEEE Signal Process Letters, 16 (2009), 38-40.   Google Scholar

[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.  Google Scholar

[25]

R. J. Turyn, The linear complexity of the Legendre sequence, J. Soc. Ind. Appl. Math., 12 (1964), 115-116.  doi: 10.1137/0112010.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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 2n-periodic binary sequences. Journal of Industrial & 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 2n-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, 2020  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 & Games, 2018, 5 (2) : 165-185. doi: 10.3934/jdg.2018010

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (356)
  • HTML views (178)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy