On linear complexity of sequences over \(\text{GF}(2^n)\) (Q818141)

The paper studies the effect, on the linear complexity of a sequence over the field \(\mathbb F_{2^n}\), of a change of basis in the extension \(\mathbb F_{2^n}| \mathbb F_2\). The linear complexity of a (pseudorandom) sequence over the finite field \(\mathbb F_q\)\, is the length of the shortest linear feedback shift register which can produce that sequence, or the degree of the minimal polynomial of the sequence. Such sequences are employed as keys in Stream Cipher Cryptography. Security reasons show the convenience of choosing sequences with linear complexity \(l\)\, as large as possible (the Berlekamp-Massey algorithm allows a cryptanalyst, knowing \(2l\)\, fields elements of the sequence to recover the minimal polynomial (and so the entire sequence), see [\textit{R. Lidl} and \textit{H. Niederreiter}, Finite fields. 2nd ed. Encyclopedia of Mathematics and its Applications, Cambridge Univ. Press (1996; Zbl 0866.11069)]. As the authors point out the linear complexity of a sequence over \(\mathbb F_{2^n}\), given in binary representation, depend on the chosen basis of \(\mathbb F_{2^n}| \mathbb F_2\). The purpose of the paper is then to study the relationship among the minimal polynomials of a given sequence for two different basis. After considering the relation between two sequences \({\mathbf a}, {\mathbf b}\), whose elements are obtained from the same binary representation but in two different basis, the main result of the paper (Theorem~1) gives the minimal polynomial \(g(X)\)\, corresponding to \({\mathbf b}\)\, as the lcm of the minimal polynomial \(f(X)\)\, of \({\mathbf a}\)\, and certain transforms of it. The authors also point out that these results can be extended to sequences over \(\mathbb F_{p^n}\)\, and over Galois rings.