Fourier transforms and the 2-adic span of periodic binary sequences

In this paper we develop an arithmetic analog of Blahut´s theorem (Blahut 1979, Massey 1986) which says that the linear complexity (or equivalent linear span) λ(S) of a periodic binary sequence S=a ₀,a₁,… is equal to the number of nonzero coefficients in the discrete Fourier transform (DFT) of S. If S is used as the key in a stream cipher then λ(S) is a measure of the security of S against a cryptoanalytic attack: a linear feedback shift register (LFSR) that generates S can be determined from 2λ(S) bits of S by using the Berlekamp-Massey algorithm, and the resulting shift register will have length λ(S). So Blahut´s theorem makes precise the common observation that a “complex” signal is one with many nonzero Fourier components