The minimal polynomial of sequence obtained from componentwise linear transformation of linear recurring sequence

DOI10.1016/J.TCS.2010.07.014arXiv0912.0312MaRDI QIDQ6216552FDOQ6216552

Authors: Zhihan Gao, Fangwei Fu 

Publication date: 1 December 2009

Abstract: Let $S=(s_1,s_2,\mathrm{...},s_m,\mathrm{...})$ be a linear recurring sequence with terms in $GF(q^n)$ and $T$ be a linear transformation of $GF(q^n)$ over $GF(q)$. Denote $T(S)=(T(s_1),T(s_2),\mathrm{...},T(s_m),\mathrm{...})$. In this paper, we first present counter examples to show the main result in [A.M. Youssef and G. Gong, On linear complexity of sequences over $GF(2^n)$, Theoretical Computer Science, 352(2006), 288-292] is not correct in general since Lemma 3 in that paper is incorrect. Then, we determine the minimal polynomial of $T(S)$ if the canonical factorization of the minimal polynomial of $S$ without multiple roots is known and thus present the solution to the problem which was mainly considered in the above paper but incorrectly solved. Additionally, as a special case, we determine the minimal polynomial of $T(S)$ if the minimal polynomial of $S$ is primitive. Finally, we give an upper bound on the linear complexity of $T(S)$ when $T$ exhausts all possible linear transformations of $GF(q^n)$ over $GF(q)$. This bound is tight in some cases.

Mathematics Subject Classification ID

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

This page was built for publication: The minimal polynomial of sequence obtained from componentwise linear transformation of linear recurring sequence

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