In this paper, the construction of finite-length binary sequences whose nonlinear complexity is not less than half of the length is investigated. By characterizing the structure of the sequences, an algorithm is proposed to generate all binary sequences with length$n$and nonlinear complexity$c\geq n/2$, where$n$is an integer larger than 2. Furthermore, a formula is established to calculate the exact number of these sequences. The distribution of nonlinear complexity for these sequences is thus completely determined.

Let 11φ(p-1)n) defined by sn≡ gn+1+gn+2mod 2, n=0,1,⋯ In particular, we study the balance, linear complexity and 2-adic complexity of (sn). We show that for a typical p the sequence (sn) is quite unbalanced. However, there are still infinitely many p such that (sn) is very balanced. We also prove similar results for the distribution of longer patterns. Moreover, we give general lower bounds on the linear complexity and 2-adic complexity of (sn) and state sufficient conditions for attaining their maximums. Hence, for carefully chosen p, these sequences are attractive candidates for cryptographic applications.