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)

Warning
There is a more recent version of this item available.
[thumbnail of FFA-Ferruh.pdf] PDF
FFA-Ferruh.pdf

Download (250kB)

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
Divisions: Faculty of Engineering and Natural Sciences
Depositing User: Wilfried Meidl
Date Deposited: 07 Nov 2008 17:11
Last Modified: 17 Jul 2019 16:43
URI: https://research.sabanciuniv.edu/id/eprint/9794

Available Versions of this Item

Actions (login required)

View Item
View Item