The nonlinear complexity of level sequences over Z/(4)

AbstractFor any sequence a̲ over Z/(22), there is an unique 2-adic expansion a̲=a̲0+a̲1·2, where a̲0 and a̲1 are sequences over {0,1} and can be regarded as sequences over the binary field GF(2) naturally. We call a̲0 and a̲1 the level sequences of a̲. Let f(x) be a primitive polynomial of degree n over Z/(22), and a̲ be a primitive sequence generated by f(x). In this paper, we discuss how many bits of a̲1 can determine uniquely the original primitive sequence a̲. This issue is equivalent with one to estimate the whole nonlinear complexity, NL(f(x),22), of all level sequences of f(x). We prove that 4n is a tight upper bound of NL(f(x),22) if f(x)(mod2) is a primitive trinomial over GF(2). Moreover, the experimental result shows that NL(f(x),22) varies around 4n if f(x)(mod2) is a primitive polynomial over GF(2). From this result, we can deduce that NL(f(x),22) is much smaller than L(f(x),22), where L(f(x),22) is the linear complexity of level sequences of f(x)