From the introduction: Let \(S=a_0,a_1,\dots\) be a periodic binary sequence with period \(L\). The linear span of \(S\), denoted \(\lambda (S)\), is the length of the shortest linear recurrence satisfied by \(S\) or, equivalently, the size of the smallest linear feedback shift register that generates \(S\). It is an important measure of the complexity of a sequence, and it is used in a number of engineering applications. For example, suppose that \(S\) is to be used as the key in a stream cipher. The Berlekamp-Massey algorithm can be used by a cryptanalyst to recover the sequence once \(2\lambda (S)\) bits of \(S\) are known. Thus \(S\) is secure only if \(\lambda(S)\) is large.
Let \(\tau\) be a primitive \(L\)th root of unity in some field extension \(F\) of GF(2). (Such a \(\tau\) exists if and only if \(L\) is odd.) The \(k\)th discrete Fourier coefficient of \(S\) is \(\overline a_k=\sum^{L-1}_{i=0} a_i\tau^{k_i} \in F\). Blahut’s theorem says that the linear span of \(S\) is equal to the number of nonzero discrete Fourier coefficients of \(S\). The purpose of this correspondence is to develop an arithmetic analog of Blahut’s theorem [R. Blahu, IBM J. Res. Dev. 23, 299-315 (1979; Zbl 0403.94012) and J. Massey, ‘Cryptography and system theory’ in Proc. 24th Allerton Conf. Commun. Control Comput., Oct. 1-3, 1986 (1986)].