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

Lin Yi; Xiangyong Zeng; Zhimin Sun

doi:10.3934/amc.2020091

Article Contents

2021, Volume 15, Issue 4: 701-720. Doi: 10.3934/amc.2020091

This issue Previous Article Information set decoding in the Lee metric with applications to cryptography Next Article A generic construction of rotation symmetric bent functions

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

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

^* Corresponding author: Xiangyong Zeng
^* Corresponding author: Xiangyong Zeng

Received: August 31, 2019

Revised: February 29, 2020

Early access: July 2020

Published: November 2021

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

Abstract

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:

Full Text(HTML)

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

Related Papers

Cited by

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.