On evaluating the linear complexity of a sequence of least period 2 n

The linear complexity of a periodic binary sequence is the length of the shortest linear feedback shift register that can be used to generate that sequence. When the sequence has least period 2ⁿ,n0, there is a fast algorithm due to Games and Chan that evaluates this linear complexity. In this paper a related algorithm is presented that obtains the linear complexity of the sequence requiring, on average for sequences of period 2ⁿ,n0, no more than 2 parity checks sums.