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

摘要

Let S = (s_1, s_2, ..., s_m,...) 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),..., T(s_m),...). In this paper, we first present counter examples to show that the main result in [A.M. Youssef, G. Gong, On linear complexity of sequences over GF(2~n), Theoret. Comput. Sci., 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 main problem which was 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.