American Institute of Mathematical Sciences

Advanced
doi: 10.3934/amc.2020091

On finite length nonbinary sequences with large nonlinear complexity over the residue ring $ \mathbb{Z}_{m} $

Lin Yi , Xiangyong Zeng , and  Zhimin Sun

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

* Corresponding author: Xiangyong Zeng

Received  September 2019 Revised  March 2020 Published  July 2020

Fund Project: L. Yi and Z. Sun were supported by the Natural Science Foundation of Hubei province of China (2019CFB543). X. Zeng was supported by Major Technological Innovation Special Project of Hubei Province (No. 2019ACA144)

In this paper, we characterize all nonbinary sequences of length $ n $ with nonlinear complexity $ n-4 $ for $ n\geq9 $ and establish a formula on the number of such sequences. More generally, we characterize other finite length nonbinary sequences with large nonlinear complexity over $ \mathbb{Z}_{m} $.

Keywords: Finite length sequence, nonbinary sequence over $ \mathbb{Z}_{m} $, nonlinear complexity, $ k $-error nonlinear complexity, feedback shift register.
Mathematics Subject Classification: Primary: 94A55; Secondary: 94A60.
Citation: 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, doi: 10.3934/amc.2020091
References:
[1]

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

[2]

O. Geil, O. Ferruh and D. Ruano, Constructing sequences with high nonlinear complexity using the Weierstrass semigroup of a pair of distinct points of a hermitian curve, Semigroup Forum, 98 (2019), 543-555.  doi: 10.1007/s00233-018-9976-8.  Google Scholar

[3]

C. J. A. Jansen, Investigations on Nonlinear Streamciper Systems: Construction and Evaluation Methods, Ph.D thesis, Dept. Elect. Eng., TU Delft, Delft, The Netherlands, 1989.  Google Scholar

[4]

C. J. A. Jansen and D. E. Boekee, The shortest feedback shift register that can generate a given sequence, in Advanced in Cryptography - CRYPTO'89, LNCS 435 (1990), 90–99. doi: 10.1007/0-387-34805-0_10.  Google Scholar

[5]

N. Li and X. Tang, On the linear complexity of binary sequences of period $4N$ with optimal autocorrelation value/magnitude, IEEE Trans. Inf. Theory, 57 (2011), 7597-7604.  doi: 10.1109/TIT.2011.2159575.  Google Scholar

[6]

K. Limniotis, N. Kolokotronis and N. Kalouptsidis, On the nonlinear complexity and lempel-Ziv complexity of finite length sequences, IEEE Trans. Inf. Theory, 53 (2007), 4293-4302.  doi: 10.1109/TIT.2007.907442.  Google Scholar

[7]

Y. Luo, C. Xing and L. You, Construction of sequences with high nonlinear complexity from function fields, IEEE Trans. Inf. Theory, 63 (2017), 7646-7650.  doi: 10.1109/TIT.2017.2736545.  Google Scholar

[8]

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

[9]

W. Meidl and A. Winterhof, On the linear complexity profile of some new explicit inversive pseudorandom numbers, J. Complexity, 20 (2004), 350-355.  doi: 10.1016/j.jco.2003.08.017.  Google Scholar

[10]

H. Niderreiter, Linear complexity and related complexity measures for sequences, Progress in Cryptology - INDOCRYPT 2003, LNCS 2904 (2003), 1–17. doi: 10.1007/978-3-540-24582-7_1.  Google Scholar

[11]

H. Niderreiter and C. Xing, Sequences with high nonlinear complexity, IEEE Trans. Inf. Theory, 60 (2014), 6696-6701.  doi: 10.1109/TIT.2014.2343225.  Google Scholar

[12]

J. Peng, X. Zeng and Z. Sun, Finite length sequences with large nonlinear complexity, Advance in Mathematics of Communication, 12 (2018), 215-230.  doi: 10.3934/amc.2018015.  Google Scholar

[13]

P. Rizomiliotis, Constructing periodic binary sequences with maximum nonlinear span, IEEE Trans. Inf. Theory, 52 (2006), 4257-4261.  doi: 10.1109/TIT.2006.880054.  Google Scholar

[14]

P. Rizomiliotis and N. Kalouptsidis, Results on the nonlinear span of binary sequences, IEEE Trans. Inf. Theory, 51 (2005), 1555-1563.  doi: 10.1109/TIT.2005.844090.  Google Scholar

[15]

Z. Sun, X. Zeng, C. Li and T. Helleseth, Investigations on periodic sequences with maximum nonlinear complexity, IEEE Trans. Inf. Theory, 63 (2017), 6188-6198.  doi: 10.1109/TIT.2017.2714681.  Google Scholar

[16]

Z. Xiao, X. Zeng, C. Li and Y. Jiang, Binary sequences with period $N$ and nonlinear complexity $N-2$, Cryptography and Communications, 11 (2019), 735-757.  doi: 10.1007/s12095-018-0324-3.  Google Scholar

show all references

References:
[1]

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

[2]

O. Geil, O. Ferruh and D. Ruano, Constructing sequences with high nonlinear complexity using the Weierstrass semigroup of a pair of distinct points of a hermitian curve, Semigroup Forum, 98 (2019), 543-555.  doi: 10.1007/s00233-018-9976-8.  Google Scholar

[3]

C. J. A. Jansen, Investigations on Nonlinear Streamciper Systems: Construction and Evaluation Methods, Ph.D thesis, Dept. Elect. Eng., TU Delft, Delft, The Netherlands, 1989.  Google Scholar

[4]

C. J. A. Jansen and D. E. Boekee, The shortest feedback shift register that can generate a given sequence, in Advanced in Cryptography - CRYPTO'89, LNCS 435 (1990), 90–99. doi: 10.1007/0-387-34805-0_10.  Google Scholar

[5]

N. Li and X. Tang, On the linear complexity of binary sequences of period $4N$ with optimal autocorrelation value/magnitude, IEEE Trans. Inf. Theory, 57 (2011), 7597-7604.  doi: 10.1109/TIT.2011.2159575.  Google Scholar

[6]

K. Limniotis, N. Kolokotronis and N. Kalouptsidis, On the nonlinear complexity and lempel-Ziv complexity of finite length sequences, IEEE Trans. Inf. Theory, 53 (2007), 4293-4302.  doi: 10.1109/TIT.2007.907442.  Google Scholar

[7]

Y. Luo, C. Xing and L. You, Construction of sequences with high nonlinear complexity from function fields, IEEE Trans. Inf. Theory, 63 (2017), 7646-7650.  doi: 10.1109/TIT.2017.2736545.  Google Scholar

[8]

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

[9]

W. Meidl and A. Winterhof, On the linear complexity profile of some new explicit inversive pseudorandom numbers, J. Complexity, 20 (2004), 350-355.  doi: 10.1016/j.jco.2003.08.017.  Google Scholar

[10]

H. Niderreiter, Linear complexity and related complexity measures for sequences, Progress in Cryptology - INDOCRYPT 2003, LNCS 2904 (2003), 1–17. doi: 10.1007/978-3-540-24582-7_1.  Google Scholar

[11]

H. Niderreiter and C. Xing, Sequences with high nonlinear complexity, IEEE Trans. Inf. Theory, 60 (2014), 6696-6701.  doi: 10.1109/TIT.2014.2343225.  Google Scholar

[12]

J. Peng, X. Zeng and Z. Sun, Finite length sequences with large nonlinear complexity, Advance in Mathematics of Communication, 12 (2018), 215-230.  doi: 10.3934/amc.2018015.  Google Scholar

[13]

P. Rizomiliotis, Constructing periodic binary sequences with maximum nonlinear span, IEEE Trans. Inf. Theory, 52 (2006), 4257-4261.  doi: 10.1109/TIT.2006.880054.  Google Scholar

[14]

P. Rizomiliotis and N. Kalouptsidis, Results on the nonlinear span of binary sequences, IEEE Trans. Inf. Theory, 51 (2005), 1555-1563.  doi: 10.1109/TIT.2005.844090.  Google Scholar

[15]

Z. Sun, X. Zeng, C. Li and T. Helleseth, Investigations on periodic sequences with maximum nonlinear complexity, IEEE Trans. Inf. Theory, 63 (2017), 6188-6198.  doi: 10.1109/TIT.2017.2714681.  Google Scholar

[16]

Z. Xiao, X. Zeng, C. Li and Y. Jiang, Binary sequences with period $N$ and nonlinear complexity $N-2$, Cryptography and Communications, 11 (2019), 735-757.  doi: 10.1007/s12095-018-0324-3.  Google Scholar

Table 1.  Binary sequences of length 13 with nonlinear complexity 9 and their distribution
set Sequences $ \# $ Seq.
$ E_3(A_{10}) $ 0000000001000, 0000000001100, 0000000001010, 0000000001110, 0000000001001
0000000001101, 0000000001011, 0000000001111, 1111111110000, 1111111110100 16
1111111110010, 1111111110110, 1111111110001, 1111111110101, 1111111110011
1111111110111
$ E_2(A_{11}) $ 0101010101100, 0101010101110, 0101010101101, 0101010101111, 0111111111000
0111111111010, 0111111111001, 0111111111011, 1010101010000, 1010101010010 16
1010101010001, 1010101010011, 1000000000100, 1000000000110, 1000000000101
1000000000111
$ E_1(A_{12}) $ 0010010010000, 0010010010001, 0010101010110, 0010101010111, 0011111111100
0011111111101, 1101101101110, 1101101101111, 1101010101000, 1101010101001 24
1100000000010, 1100000000011, 0100100100110, 0100100100111, 0100000000010
0100000000011, 1011011011000, 1011011011001, 1011111111100, 1011111111101
0110110110100, 0110110110101, 1001001001010, 1001001001011
$ B_1 $ 0011001100111, 0011011011010, 1100110011000, 1100100100101, 0110011001101 8
0110000000001, 1001100110010, 1001111111110
$ B_2 $ 0001000100011, 0001001001000, 0001010101011, 0001111111110, 1110111011100
1110110110111, 1110101010100, 1110000000001, 0010001000101, 0010000000001
1101110111010, 1101111111110, 0100010001001, 1011101110110, 0101101101100 22
0101111111110, 1010010010011, 1010000000001, 0110101010100, 1001010101011
0111011101111, 1000100010000
Table Options

Download as excel

set Sequences $ \# $ Seq.
$ E_3(A_{10}) $ 0000000001000, 0000000001100, 0000000001010, 0000000001110, 0000000001001
0000000001101, 0000000001011, 0000000001111, 1111111110000, 1111111110100 16
1111111110010, 1111111110110, 1111111110001, 1111111110101, 1111111110011
1111111110111
$ E_2(A_{11}) $ 0101010101100, 0101010101110, 0101010101101, 0101010101111, 0111111111000
0111111111010, 0111111111001, 0111111111011, 1010101010000, 1010101010010 16
1010101010001, 1010101010011, 1000000000100, 1000000000110, 1000000000101
1000000000111
$ E_1(A_{12}) $ 0010010010000, 0010010010001, 0010101010110, 0010101010111, 0011111111100
0011111111101, 1101101101110, 1101101101111, 1101010101000, 1101010101001 24
1100000000010, 1100000000011, 0100100100110, 0100100100111, 0100000000010
0100000000011, 1011011011000, 1011011011001, 1011111111100, 1011111111101
0110110110100, 0110110110101, 1001001001010, 1001001001011
$ B_1 $ 0011001100111, 0011011011010, 1100110011000, 1100100100101, 0110011001101 8
0110000000001, 1001100110010, 1001111111110
$ B_2 $ 0001000100011, 0001001001000, 0001010101011, 0001111111110, 1110111011100
1110110110111, 1110101010100, 1110000000001, 0010001000101, 0010000000001
1101110111010, 1101111111110, 0100010001001, 1011101110110, 0101101101100 22
0101111111110, 1010010010011, 1010000000001, 0110101010100, 1001010101011
0111011101111, 1000100010000
[1]

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
[2]

Alexander Zeh, Antonia Wachter. Fast multi-sequence shift-register synthesis with the Euclidean algorithm. Advances in Mathematics of Communications, 2011, 5 (4) : 667-680. doi: 10.3934/amc.2011.5.667
[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]

Yuhua Sun, Zilong Wang, Hui Li, Tongjiang Yan. The cross-correlation distribution of a $p$-ary $m$-sequence of period $p^{2k}-1$ and its decimated sequence by $\frac{(p^{k}+1)^{2}}{2(p^{e}+1)}$. Advances in Mathematics of Communications, 2013, 7 (4) : 409-424. doi: 10.3934/amc.2013.7.409
[6]

Hua Liang, Wenbing Chen, Jinquan Luo, Yuansheng Tang. A new nonbinary sequence family with low correlation and large size. Advances in Mathematics of Communications, 2017, 11 (4) : 671-691. doi: 10.3934/amc.2017049
[7]

R. P. Gupta, Peeyush Chandra, Malay Banerjee. Dynamical complexity of a prey-predator model with nonlinear predator harvesting. Discrete & Continuous Dynamical Systems - B, 2015, 20 (2) : 423-443. doi: 10.3934/dcdsb.2015.20.423
[8]

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
[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]

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
[11]

Steven T. Dougherty, Cristina Fernández-Córdoba. Codes over $\mathbb{Z}_{2^k}$, Gray map and self-dual codes. Advances in Mathematics of Communications, 2011, 5 (4) : 571-588. doi: 10.3934/amc.2011.5.571
[12]

Yuan Cao, Yonglin Cao, Hai Q. Dinh, Ramakrishna Bandi, Fang-Wei Fu. An explicit representation and enumeration for negacyclic codes of length $ 2^kn $ over $ \mathbb{Z}_4+u\mathbb{Z}_4 $. Advances in Mathematics of Communications, 2021, 15 (2) : 291-309. doi: 10.3934/amc.2020067
[13]

Wenbing Chen, Jinquan Luo, Yuansheng Tang, Quanquan Liu. Some new results on cross correlation of $p$-ary $m$-sequence and its decimated sequence. Advances in Mathematics of Communications, 2015, 9 (3) : 375-390. doi: 10.3934/amc.2015.9.375
[14]

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
[15]

Hai Q. Dinh, Bac T. Nguyen, Paravee Maneejuk. Constacyclic codes of length $ 8p^s $ over $ \mathbb F_{p^m} + u\mathbb F_{p^m} $. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020123
[16]

Yonglin Cao, Yuan Cao, Hai Q. Dinh, Fang-Wei Fu, Jian Gao, Songsak Sriboonchitta. Constacyclic codes of length $np^s$ over $\mathbb{F}_{p^m}+u\mathbb{F}_{p^m}$. Advances in Mathematics of Communications, 2018, 12 (2) : 231-262. doi: 10.3934/amc.2018016
[17]

Markus Dick, Martin Gugat, Günter Leugering. Classical solutions and feedback stabilization for the gas flow in a sequence of pipes. Networks & Heterogeneous Media, 2010, 5 (4) : 691-709. doi: 10.3934/nhm.2010.5.691
[18]

Thomas Feulner. Canonization of linear codes over $\mathbb Z$4. Advances in Mathematics of Communications, 2011, 5 (2) : 245-266. doi: 10.3934/amc.2011.5.245
[19]

Natalie Priebe Frank, Lorenzo Sadun. Topology of some tiling spaces without finite local complexity. Discrete & Continuous Dynamical Systems, 2009, 23 (3) : 847-865. doi: 10.3934/dcds.2009.23.847
[20]

Jeong-Yup Lee, Boris Solomyak. On substitution tilings and Delone sets without finite local complexity. Discrete & Continuous Dynamical Systems, 2019, 39 (6) : 3149-3177. doi: 10.3934/dcds.2019130

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (64)
  • HTML views (382)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences