Joint linear complexity of arbitrary multisequences consisting of linear recurring sequences

DOI10.1016/J.FFA.2009.03.001MaRDI QIDQ841240zbMATH OpenOpenAlexFDO

Authors Fangwei Fu, Harald Niederreiter, Ferruh Özbudak

Publication date 15 September 2009

Published in Finite Fields and their Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ffa.2009.03.001

zbMATH Keywords

expectationjoint linear complexitylinear recurring sequencesrandom multisequencesvariance

Mathematics Subject Classification ID

Recurrences (11B37) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Shift register sequences and sequences over finite alphabets in information and communication theory (94A55) Cryptography (94A60)

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\).

Recommendations

• On the Joint Linear Complexity of Linear Recurring Multisequences
• Joint linear complexity of multisequences consisting of linear recurring sequences
• Linear complexity over \(\mathbb F_q\) and over \(\mathbb F_{q^m}\) for linear recurring sequences
• Discrete Fourier Transform, Joint Linear Complexity and Generalized Joint Linear Complexity of Multisequences
• The asymptotic behavior of the joint linear complexity profile of multisequences

Cites work

• Asymptotic Behavior of Normalized Linear Complexity of Multi-sequences
• Enumeration results on the joint linear complexity of multisequences
• On the Joint Linear Complexity of Linear Recurring Multisequences
• The asymptotic behavior of the joint linear complexity profile of multisequences
• The expectation and variance of the joint linear complexity of random periodic multisequences
• The expected value of the joint linear complexity of periodic multisequences

Cited in

(12)

• The minimal polynomial over \(\mathbb F_q\) of linear recurring sequence over \(\mathbb F_{q^m}\)
• A remark on the minimal polynomial of the product of linear recurring sequences
• The expected value of the joint linear complexity of periodic multisequences
• A complexity measure for families of binary sequences
• Multidimensional linear complexity analysis of periodic arrays
• Classification and counting on multi-continued fractions and its application to multi-sequences
• Linear complexity over \(\mathbb F_q\) and over \(\mathbb F_{q^m}\) for linear recurring sequences
• Spectra of a class of quadratic functions: average behaviour and counting functions
• On the Joint Linear Complexity of Linear Recurring Multisequences
• Improved results on the probabilistic theory of the joint linear complexity of multisequences
• Discrete Fourier Transform, Joint Linear Complexity and Generalized Joint Linear Complexity of Multisequences
• The asymptotic behavior of the joint linear complexity profile of multisequences

This page was built for publication: Joint linear complexity of arbitrary multisequences consisting of linear recurring sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q841240)