Joint linear complexity of arbitrary multisequences consisting of linear recurring sequences
type: Item
instance of: scholarly article
title: Joint linear complexity of arbitrary multisequences consisting of linear recurring sequences
zbMATH Open document ID: 1183.94015
author: Fangwei Fu
author: Harald Niederreiter
author: Ferruh Özbudak
published in: Finite Fields and their Applications
publication date: 2009-09-15T00:00:00Z
review text: Let \(g_1,\dots,g_s\in{\mathbb F}_q\) be arbitrary monic polynomials each of degree at least one. Let \({\mathcal M}(g_1,\dots,g_s)\) denote the set of \(s\)-fold multisequences \((\sigma_1,\dots,\sigma_s)\) such that \(\sigma_i\) is a linear recurring sequence over \({\mathbb F}_q\) with characteristic polynomial \(g_i\) for each \(1\leq i\leq s\). Let \(\Phi(d;g_1,\dots,g_s)\) denote the number of multisequences from \({\mathcal M}(g_1,\dots,g_s)\) with joint minimal polynomial \(d\in{\mathbb F}_q\). The main results of the paper give a formula for the counting function \(\Phi(d;g_1,\dots,g_s)\) and the expectation and the variance of the joint linear complexity of random multisequences that are uniformly distributed over \({\mathcal M}(g_1,\dots,g_s)\), where \(g\)'s are arbitrary nonconstant monic polynomials over \({\mathbb F}_q\) all in terms of parameters involving the factorizations of \(g_1,\dots,g_s\) and \(d\).
Mathematics Subject Classification ID: 94A55
Mathematics Subject Classification ID: 11T71
Mathematics Subject Classification ID: 11B37
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 5603987
zbMATH Keywords: joint linear complexity
zbMATH Keywords: random multisequences
zbMATH Keywords: linear recurring sequences
zbMATH Keywords: expectation
zbMATH Keywords: variance
reviewed by: Štefan Porubský
MaRDI profile type: Publication
full work available at URL: j.ffa.2009.03.001
OpenAlex ID: W2154477824
cites work: Asymptotic Behavior of Normalized Linear Complexity of Multi-sequences
cites work: On the Joint Linear Complexity of Linear Recurring Multisequences
cites work: The expectation and variance of the joint linear complexity of random periodic multisequences
cites work: The expected value of the joint linear complexity of periodic multisequences
cites work: The asymptotic behavior of the joint linear complexity profile of multisequences
cites work: Enumeration results on the joint linear complexity of multisequences
DOI: 10.1016/J.FFA.2009.03.001
description: scientific article; zbMATH DE number 5603987