Linear complexity over Fq and over Fqm for linear recurring sequences

Since the Fq-linear spaces and Fqm are isomorphic, an m-fold multisequence S over the finite field Fq with a given characteristic polynomial f∈Fq[x], can be identified with a single sequence S over Fqm with characteristic polynomial f. The linear complexity of S, which will be called the generalized joint linear complexity of S, can be significantly smaller than the conventional joint linear complexity of S. We determine the expected value and the variance of the generalized joint linear complexity of a random m-fold multisequence S with given minimal polynomial. The result on the expected value generalizes a previous result on periodic m-fold multisequences. Moreover we determine the expected drop of linear complexity of a random m-fold multisequence with given characteristic polynomial f, when one switches from conventional joint linear complexity to generalized joint linear complexity.