# 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)

 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 UNSPECIFIED 9794 Wilfried Meidl 07 Nov 2008 17:11 29 Apr 2009 10:21

### Available Versions of this Item

Repository Staff Only: item control page