On linear complexity of sequences over GF(2ⁿ)
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.
- Reducing the Computation of Linear Complexities of Periodic Sequences Over ${\hbox {GF}}(p^m)$
- Linear complexity of binary generalized cyclotomic sequences over \(\mathrm{GF}(q)\)
- On the Linear Complexity of Combined Shift Register Sequences
- Linear complexity of a class of pseudorandom sequences over a general finite field
- A relationship between linear complexity and k-error linear complexity
- scientific article; zbMATH DE number 3882549 (Why is no real title available?)
- scientific article; zbMATH DE number 4083539 (Why is no real title available?)
- scientific article; zbMATH DE number 954401 (Why is no real title available?)
- Linear Complexity and Random Sequences
- Relationships between m-sequences over GF(q) and GF(q/sup m/)
- Shift Register Synthesis (Modulo m)
- Shift-register synthesis and BCH decoding
- On the linear complexity of Hall's sextic residue sequences over \(\mathrm{GF}(q)\)
- Linear recurring sequences and subfield subcodes of cyclic codes
- The minimal polynomial of a sequence obtained from the componentwise linear transformation of a linear recurring sequence
- On the complexity of a family of \(k\)-context-free sequences
- On the linear complexity of some new q-ary sequences
This page was built for publication: On linear complexity of sequences over \(\text{GF}(2^n)\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q818141)
