Linear complexity of a sequence

For a shift register sequence $\mathbf{a}$, the linear complexity $L ( \mathbf{a} )$ is just the degree of its minimal polynomial $m$, i.e. the length of a shortest linear feedback shift register (LFSR; cf. Shift register sequence) capable of producing $\mathbf{a}$. The linear complexity also equals the maximum number of linearly independent vectors among the state vectors

\begin{equation*} {\bf a}^ { ( t ) } = ( a _ { t } , a _ { t + 1} , \dots , a _ { n + t - 1 }) ( t \geq 0 ) \end{equation*}

of an arbitrary LFSR of length $n$ associated with $\mathbf{a}$.

Now, let $\mathbf{a}$ denote either a finite sequence $( a _ { k } ) _ { k = 0 , \dots , N - 1}$ of length $N$ or an infinite sequence $( a _ { k } ) _ { k \geq 0}$ over a Galois field ${F} = \operatorname{GF} ( q )$ (in the latter case, put $N = \infty$). For every positive integer $k < N$, denote by $L _ { k } ( \mathbf{a} )$ the length of an LFSR $\Lambda _ { k } ( \mathbf{a} )$ of least length over $F$ capable of producing a shift register sequence ${\bf s} ^ { ( k ) }$ which agrees with $\mathbf{a}$ for the first $k$ entries $a _{0} , \dots , a _ { k - 1 }$. In this way, one obtains a sequence $\mathbf{L} = ( L _ { k } ( \mathbf a ) )$ of the same length $N$, which is called the linear complexity profile of $\mathbf{a}$. Then one defines the linear complexity $L ( \mathbf{a} )$ of $\mathbf{a}$ as the maximum value of all $L _ { k } ( \mathbf{a} )$ if these values are bounded, and as $\infty$ otherwise. Thus, $L ( \mathbf{a} ) = \infty$ if and only if $\mathbf{a}$ is an infinite sequence which is not ultimately periodic (cf. Ultimately periodic sequence), and $L ( \mathbf{a} ) = L _ { N } ( \mathbf{a} )$ if $\mathbf{a}$ is a finite sequence of length $N$. Hence the linear complexity profile constitutes a refinement of the linear complexity of a sequence. The linear complexity profile of $\mathbf{a}$ and the associated sequence of LFSRs $\Lambda _ { k } ( \mathbf{a} )$ can be computed efficiently by the celebrated Berlekamp–Massey algorithm, see [a1] or [a2].

The linear complexity of a sequence is an important aspect in judging its suitability for use in cryptography. A high linear complexity by itself does not guarantee any randomness properties of the sequence considered. The linear complexity profiles of binary random sequences are analyzed in [a3], Chap. 4, where it is shown that a binary random sequence $\mathbf{a}$ of length $N$ usually has linear complexity very close to $N / 2$ with the complexity profile growing in a roughly (but not exactly!) continuous manner (so that $L _ { k } ( \mathbf{a} )$ is close to $k / 2$). Moreover, using $\mathbf{a}$ to generate a periodic sequence $\mathbf{s}$ with period $N$ results in a linear complexity close to $N$, provided that $N$ is a power of $2$ or a Mersenne prime number (cf. Mersenne number). Consequently, a periodic binary sequence with good randomness properties should have complexity close to the period length and a profile growing more or less smoothly.

References

[a1]	R.E. Blahut, "Theory and practice of error control codes" , Addison-Wesley (1983)
[a2]	D. Jungnickel, "Finite fields: Structure and arithmetics" , Bibliographisches Inst. Mannheim (1993)
[a3]	R. Rueppel, "Analysis and design of stream ciphers" , Springer (1986)