I. Introduction
Binary sequences with good pseudorandomness and complexity properties are widely used as keystreams in cryptographic applications [11], [16]. Among the measures commonly used to measure the complexity of a sequence is its linear complexity , defined to be the length of the shortest linear feedback shift register that generates . Sequences of low linear complexity are fully determined via a solution of linear equations if consecutive terms of the sequence are known. Hence, high linear complexity is a prerequisite for cryptographic applications. If a sequence has period , the Berlekamp–Massey algorithm requires operations [10] to determine its linear complexity. If , for , then the linear complexity is more efficiently computed via the Games–Chan algorithm, which has complexity [5]. Although the latter requires knowledge of the entire period, and thus is not practical from a cryptographic point of view, it reveals important properties that can be used in constructions of sequences and arrays with certain window properties [3], [15]. Rueppel [16] introduced the notion of the linear complexity profile that describes how the linear complexity grows in terms of the sequence length.