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]

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

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

Jie Li, Xiangdong Ye, Tao Yu. Mean equicontinuity, complexity and applications. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 359-393. doi: 10.3934/dcds.2020167
[4]

Hongwei Liu, Jingge Liu. On $ \sigma $-self-orthogonal constacyclic codes over $ \mathbb F_{p^m}+u\mathbb F_{p^m} $. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020127
[5]

Junchao Zhou, Yunge Xu, Lisha Wang, Nian Li. Nearly optimal codebooks from generalized Boolean bent functions over $ \mathbb{Z}_{4} $. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020121
[6]

Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020465
[7]

Wenjun Liu, Hefeng Zhuang. Global attractor for a suspension bridge problem with a nonlinear delay term in the internal feedback. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 907-942. doi: 10.3934/dcdsb.2020147
[8]

Xuefei He, Kun Wang, Liwei Xu. Efficient finite difference methods for the nonlinear Helmholtz equation in Kerr medium. Electronic Research Archive, 2020, 28 (4) : 1503-1528. doi: 10.3934/era.2020079
[9]

Xiu Ye, Shangyou Zhang, Peng Zhu. A weak Galerkin finite element method for nonlinear conservation laws. Electronic Research Archive, 2021, 29 (1) : 1897-1923. doi: 10.3934/era.2020097
[10]

Zi Xu, Siwen Wang, Jinjin Huang. An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 971-979. doi: 10.3934/jimo.2020007
[11]

Yuanfen Xiao. Mean Li-Yorke chaotic set along polynomial sequence with full Hausdorff dimension for $ \beta $-transformation. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 525-536. doi: 10.3934/dcds.2020267
[12]

Linglong Du, Min Yang. Pointwise long time behavior for the mixed damped nonlinear wave equation in $ \mathbb{R}^n_+ $. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020033
[13]

Saadoun Mahmoudi, Karim Samei. Codes over $ \frak m $-adic completion rings. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020122
[14]

Guoliang Zhang, Shaoqin Zheng, Tao Xiong. A conservative semi-Lagrangian finite difference WENO scheme based on exponential integrator for one-dimensional scalar nonlinear hyperbolic equations. Electronic Research Archive, 2021, 29 (1) : 1819-1839. doi: 10.3934/era.2020093
[15]

Shudi Yang, Xiangli Kong, Xueying Shi. Complete weight enumerators of a class of linear codes over finite fields. Advances in Mathematics of Communications, 2021, 15 (1) : 99-112. doi: 10.3934/amc.2020045
[16]

Liupeng Wang, Yunqing Huang. Error estimates for second-order SAV finite element method to phase field crystal model. Electronic Research Archive, 2021, 29 (1) : 1735-1752. doi: 10.3934/era.2020089
[17]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077
[18]

Divine Wanduku. Finite- and multi-dimensional state representations and some fundamental asymptotic properties of a family of nonlinear multi-population models for HIV/AIDS with ART treatment and distributed delays. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021005
[19]

Gunther Uhlmann, Jian Zhai. Inverse problems for nonlinear hyperbolic equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 455-469. doi: 10.3934/dcds.2020380
[20]

Wenjun Liu, Yukun Xiao, Xiaoqing Yue. Classification of finite irreducible conformal modules over Lie conformal algebra $ \mathcal{W}(a, b, r) $. Electronic Research Archive, , () : -. doi: 10.3934/era.2020123

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (32)
  • HTML views (226)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences