title   
  

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)

WarningThere is a more recent version of this item available.

[img]
Preview
PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
244Kb

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.

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

Repository Staff Only: item control page