# American Institute of Mathematical Sciences

February  2018, 12(1): 215-230. doi: 10.3934/amc.2018015

## Finite length sequences with large nonlinear complexity

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

* Corresponding author: Zhimin Sun

Received  May 2017 Revised  November 2017 Published  March 2018

Fund Project: The authors were supported by the National Natural Science Foundation of China Grant (No. 61472120). X. Zeng and Z. Sun were also granted by National Natural Science Foundation of Hubei Province of China (No. 2017CFB143) and China Scholarship Council, respectively.

Finite length sequences with large nonlinear complexity over $\mathbb{Z}_{p}\, (p≥ 2)$ are investigated in this paper. We characterize all $p$-ary sequences of length $n$ having nonlinear complexity $n-j$ for $j=2, 3$, where $n$ is an integer satisfying $n≥ 2j$. For $n≥ 8$, all binary sequences of length $n$ with nonlinear complexity $n-4$ are obtained. Furthermore, the numbers and $k$-error nonlinear complexity of these sequences are completely determined, respectively.

Citation: 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
##### References:
 [1] C. J. A. Jansen, Investigations on Nonlinear Streamcipher Systems: Construction and Evaluation Methods, Ph. D thesis, Technical Univ. Delft, 1989.  Google Scholar [2] C. J. A. Jansen and D. E. Boekee, The shortest feedback shift register that can generate a given sequence, in Adv. Crypt. -CRYPTO'89, 1990, 90–99.  Google Scholar [3] 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.   Google Scholar [4] F. T. Macwilliams and N. J. A. Sloane, Psedo-Random sequences and arrays, Proc. IEEE, 64 (1976), 1715-1729.   Google Scholar [5] W. Meidl and A. Winterhof, On the linear complexity profile of some new explicit inverse pseudorandom numbers, J. Complexity, 20 (2004), 350-355.   Google Scholar [6] H. Niederreite, Random Number Generation and Quasi-Monte Carlo Methods, Soc. Ind. Appl. Math., Philadelphia, 1992.  Google Scholar [7] H. Niederreiter, Linear complexity and related complexity measures for sequences, in Progr. Crypt. -INDOCRYPT 2003, 2003, 1–17.  Google Scholar [8] P. Rizomiliotis, Constructing periodic binary sequences of maximum nonlinear span, IEEE Trans. Inf. Theory, 52 (2006), 4257-4261.   Google Scholar [9] P. Rizomiliotis and N. Kalouptsidis, Results on the nonlinear span of binary sequences, IEEE Trans. Inf. Theory, 51 (2005), 1555-1563.   Google Scholar [10] 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.   Google Scholar

show all references

##### References:
 [1] C. J. A. Jansen, Investigations on Nonlinear Streamcipher Systems: Construction and Evaluation Methods, Ph. D thesis, Technical Univ. Delft, 1989.  Google Scholar [2] C. J. A. Jansen and D. E. Boekee, The shortest feedback shift register that can generate a given sequence, in Adv. Crypt. -CRYPTO'89, 1990, 90–99.  Google Scholar [3] 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.   Google Scholar [4] F. T. Macwilliams and N. J. A. Sloane, Psedo-Random sequences and arrays, Proc. IEEE, 64 (1976), 1715-1729.   Google Scholar [5] W. Meidl and A. Winterhof, On the linear complexity profile of some new explicit inverse pseudorandom numbers, J. Complexity, 20 (2004), 350-355.   Google Scholar [6] H. Niederreite, Random Number Generation and Quasi-Monte Carlo Methods, Soc. Ind. Appl. Math., Philadelphia, 1992.  Google Scholar [7] H. Niederreiter, Linear complexity and related complexity measures for sequences, in Progr. Crypt. -INDOCRYPT 2003, 2003, 1–17.  Google Scholar [8] P. Rizomiliotis, Constructing periodic binary sequences of maximum nonlinear span, IEEE Trans. Inf. Theory, 52 (2006), 4257-4261.   Google Scholar [9] P. Rizomiliotis and N. Kalouptsidis, Results on the nonlinear span of binary sequences, IEEE Trans. Inf. Theory, 51 (2005), 1555-1563.   Google Scholar [10] 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.   Google Scholar
Binary sequences of length 11 with nonlinear complexity 7 and their distribution
 $Set$ Sequences # Seq. $K_1$ 00000001000, 11111110111, 00000001001, 11111110011, 00000001101 11111110110, 00000001010, 11111110101, 00000001011, 0000000110011111110100, 11111110010, 00000001110, 11111110001, 0000000111111111110000, 01010101100, 10101010011, 01010101101, 1010101001001010101110, 10101010001, 01010101111, 10101010000, 01111111000 10000000111, 01111111001, 10000000110, 01111111010, 10000000101 01111111011, 10000000100, 00100100110, 11011011001, 0010010011111011011000, 00101010110, 11010101001, 00101010111, 11010101000 00111111100, 11000000011, 00111111101, 11000000010, 01001001010 10110110101, 01001001011, 10110110100, 01000000010, 1011111110101000000011, 10111111100, 01101101110, 10010010001, 0110110111110010010000 56 $K_2$ 00110011000, 11001100111, 00110110111, 11001001000, 01100110010 10011001101, 01100000001, 10011111110 8 $K_3$ 00010001001, 11101110110, 00010010011, 11101101100, 00010101011 11101010100, 00011111110, 11100000001, 00100000001, 11011111110 00100010000, 11011101111, 01000100011, 10111011100, 0101101101010100100101, 01011111110, 10100000001, 01101010100, 10010101011 01110111010, 10001000101 22
 $Set$ Sequences # Seq. $K_1$ 00000001000, 11111110111, 00000001001, 11111110011, 00000001101 11111110110, 00000001010, 11111110101, 00000001011, 0000000110011111110100, 11111110010, 00000001110, 11111110001, 0000000111111111110000, 01010101100, 10101010011, 01010101101, 1010101001001010101110, 10101010001, 01010101111, 10101010000, 01111111000 10000000111, 01111111001, 10000000110, 01111111010, 10000000101 01111111011, 10000000100, 00100100110, 11011011001, 0010010011111011011000, 00101010110, 11010101001, 00101010111, 11010101000 00111111100, 11000000011, 00111111101, 11000000010, 01001001010 10110110101, 01001001011, 10110110100, 01000000010, 1011111110101000000011, 10111111100, 01101101110, 10010010001, 0110110111110010010000 56 $K_2$ 00110011000, 11001100111, 00110110111, 11001001000, 01100110010 10011001101, 01100000001, 10011111110 8 $K_3$ 00010001001, 11101110110, 00010010011, 11101101100, 00010101011 11101010100, 00011111110, 11100000001, 00100000001, 11011111110 00100010000, 11011101111, 01000100011, 10111011100, 0101101101010100100101, 01011111110, 10100000001, 01101010100, 10010101011 01110111010, 10001000101 22
 [1] 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 [2] 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 [3] 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 [4] 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 [5] 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 [6] 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 [7] Huaning Liu, Yixin Ren. On the pseudorandom properties of $k$-ary Sidel'nikov sequences. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021038 [8] 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 [9] Xiaoni Du, Chenhuang Wu, Wanyin Wei. An extension of binary threshold sequences from Fermat quotients. Advances in Mathematics of Communications, 2016, 10 (4) : 743-752. doi: 10.3934/amc.2016038 [10] 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, 2020  doi: 10.3934/amc.2020112 [11] Pinhui Ke, Yueqin Jiang, Zhixiong Chen. On the linear complexities of two classes of quaternary sequences of even length with optimal autocorrelation. Advances in Mathematics of Communications, 2018, 12 (3) : 525-539. doi: 10.3934/amc.2018031 [12] Denis Dmitriev, Jonathan Jedwab. Bounds on the growth rate of the peak sidelobe level of binary sequences. Advances in Mathematics of Communications, 2007, 1 (4) : 461-475. doi: 10.3934/amc.2007.1.461 [13] Arne Winterhof, Zibi Xiao. Binary sequences derived from differences of consecutive quadratic residues. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020100 [14] Xiwang Cao, Wun-Seng Chou, Xiyong Zhang. More constructions of near optimal codebooks associated with binary sequences. Advances in Mathematics of Communications, 2017, 11 (1) : 187-202. doi: 10.3934/amc.2017012 [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] Ryuji Kajikiya, Daisuke Naimen. Two sequences of solutions for indefinite superlinear-sublinear elliptic equations with nonlinear boundary conditions. Communications on Pure & Applied Analysis, 2014, 13 (4) : 1593-1612. doi: 10.3934/cpaa.2014.13.1593 [17] E. Camouzis, H. Kollias, I. Leventides. Stable manifold market sequences. Journal of Dynamics & Games, 2018, 5 (2) : 165-185. doi: 10.3934/jdg.2018010 [18] Frank Fiedler. Small Golay sequences. Advances in Mathematics of Communications, 2013, 7 (4) : 379-407. doi: 10.3934/amc.2013.7.379 [19] Yanfeng Qi, Chunming Tang, Zhengchun Zhou, Cuiling Fan. Several infinite families of p-ary weakly regular bent functions. Advances in Mathematics of Communications, 2018, 12 (2) : 303-315. doi: 10.3934/amc.2018019 [20] Lanqiang Li, Shixin Zhu, Li Liu. The weight distribution of a class of p-ary cyclic codes and their applications. Advances in Mathematics of Communications, 2019, 13 (1) : 137-156. doi: 10.3934/amc.2019008

2020 Impact Factor: 0.935

## Metrics

• HTML views (252)
• Cited by (1)

• on AIMS