\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

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

  • * Corresponding author: Xiangyong Zeng

    * Corresponding author: Xiangyong Zeng 
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)
Abstract Full Text(HTML) Figure(0) / Table(1) Related Papers Cited by
  • 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} $.

    Mathematics Subject Classification: Primary: 94A55; Secondary: 94A60.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • 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
     | Show Table
    DownLoad: CSV
  • [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. GeilO. 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. LimniotisN. 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. LuoC. 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. PengX. 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. SunX. ZengC. 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. XiaoX. ZengC. 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.
  • 加载中

Tables(1)

SHARE

Article Metrics

HTML views(796) PDF downloads(248) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return