On Functions of Linear Shift Register Sequences (Q3751507)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3987198
Language Label Description Also known as
default for all languages
No label defined
    English
    On Functions of Linear Shift Register Sequences
    scientific article; zbMATH DE number 3987198

      Statements

      On Functions of Linear Shift Register Sequences (English)
      0 references
      1986
      0 references
      periodic sequences
      0 references
      linear complexity
      0 references
      0 references
      Let \(S\) be a set of periodic sequences over \(\mathrm{GF}(q)\); the length of the shortest linear shift register over \(\mathrm{GF}(q)\) being able to produce sequences in \(S\), i.e. the degree of the minimum polynomial \(f_S\), is called the linear complexity of \(S\). This paper reviews mainly the author's work on linear complexity of sequences obtained from functions applied to linear shift register sequences. One of the main results is Theorem 3.3 [Herlestam 1982]: \(\deg f\wedge g\leq \deg f\cdot \deg g\) and the equality holds iff \(f\) or \(g\) has mere simple zeros and all zero products \(z(f)z(g)\) are different, where \(f\wedge g\) is the minimum polynomial of \(\{xy: x \in G(f), y \in G(g)\}\), \(G(h)\) is the set of all shift register sequences with \(h\) as feedback polynomial. Some sketches of proofs of the main theorems are also given. The upper bound of \(\deg f\wedge g\) above can be immediately obtained from the reviewer's ''Linear feedback shift register sequences'' (in Chinese) [Comput. Appl. Appl. Math. 10, No. 11, 21--51 (1975), {\S} 5 Theorem 2] and it is very easy to deduce a more precise upper bound from the reviewer's book ''Invertibility of finite automata'' (in Chinese) Beijing: Science Press (1979; Zbl 0609.68041), {\S} 3.6 Theorem 2]. [For the entire collection see Zbl 0583.00050.]
      0 references

      Identifiers