-
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
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 |
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.
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 2n-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 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, 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 |
2020 Impact Factor: 0.935
Tools
Metrics
Other articles
by authors
[Back to Top]