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

For any sequence over Z/(22), there is an unique 2-adic expansion , where and are sequences over {0,1} and can be regarded as sequences over the binary field GF(2) naturally. We call and the level sequences of . Let f(x) be a primitive polynomial of degree n over Z/(22), and be a primitive sequence generated by f(x). In this paper, we discuss how many bits of can determine uniquely the original primitive sequence . 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 is a primitive trinomial over GF(2). Moreover, the experimental result shows that NL(f(x),22) varies around 4n if 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).