Statistical Characteristics of the Complexity for Prime-Periodic Sequences

摘要

Using the fact that the factorization of x~N - 1 over GF(2) is especially explicit, we completely establish the distributions and the expected values of the linear complexity and the k-error linear complexity of the N-periodic sequences respectively, where N is an odd prime and 2 is a primitive root modulo N. The results show that there are a large percentage of sequences with both the linear complexity and the k-error linear complexity not less than N, quite close to their maximum possible values.