Linear complexity over F_q and over F_{q^m} for linear recurring sequences

Abstract

Since the $\F_q$-linear spaces $\F_q^m$ and $\F_{q^m}$ are isomorphic, an $m$-fold multisequence $\mathbf{S}$ over the finite field $\F_q$ with a given characteristic polynomial $f \in \F_q[x]$, can be identified with a single sequence $\mathcal{S}$ over $\F_{q^m}$ with characteristic polynomial $f$. The linear complexity of $\mathcal{S}$, which we call the generalized joint linear complexity of $\mathbf{S}$, can be significantly smaller than the conventional joint linear complexity of $\mathbf{S}$. We determine the expected value and the variance of the generalized joint linear complexity of a random $m$-fold multisequence $\mathbf{S}$ with given minimal polynomial. The result on the expected value generalizes a previous result on periodic $m$-fold multisequences. Finally 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.

Available Versions of this Item

• Linear complexity over F_q and over F_{q^m} for linear recurring sequences. (deposited 07 Nov 2008 17:11) [Currently Displayed]
  • Linear complexity over F-q and over F-qm for linear recurring sequences. (deposited 29 Apr 2009 10:21)