Linear complexity over F_q and over F_{q^m} for linear recurring sequences
Meidl, Wilfried and Özbudak, Ferruh (2008) Linear complexity over F_q and over F_{q^m} for linear recurring sequences. (Accepted/In Press) AbstractSince 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.
Item Type:  Article 

Subjects:  UNSPECIFIED 

ID Code:  9794 

Deposited By:  Wilfried Meidl 

Deposited On:  07 Nov 2008 17:11 

Last Modified:  29 Apr 2009 10:21 

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]
Repository Staff Only: item control page
