American Institute of Mathematical Sciences

Advanced
November  2021, 15(4): 701-720. 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  November 2021 Early access  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, 2021, 15 (4) : 701-720. 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.

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

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

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

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

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

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

[8]

J. L. Massey, Shift-register synthesis and BCH decoding, IEEE Trans. Inf. Theory, 15 (1969), 122-127.  doi: 10.1109/tit.1969.1054260.

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

[8]

J. L. Massey, Shift-register synthesis and BCH decoding, IEEE Trans. Inf. Theory, 15 (1969), 122-127.  doi: 10.1109/tit.1969.1054260.

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

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

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

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

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

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

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

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

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

Zhen Li, Cuiling Fan, Wei Su, Yanfeng Qi. Aperiodic/periodic complementary sequence pairs over quaternions. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021063
[12]

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

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

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

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]

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, 2022, 16 (3) : 525-570. doi: 10.3934/amc.2020123
[18]

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

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

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

2021 Impact Factor: 1.015

Tools

Metrics

  • PDF downloads (229)
  • HTML views (579)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy