I. Introduction
The linear complexity of a sequence (i.e., the length of the shortest recurrence relation, or linear feedback shift register which generates the sequence) is a fundamental parameter for virtually all applications of linearly recurrent sequences.