Permutation polynomials, de Bruijn sequences, and linear complexity
A periodic sequence \(s\) over the finite field \(F=GF(p^n)\) is called a span \(n\) de Bruijn sequence if each \(n\)-tuple of elements of \(F\) appears exactly once as a window of \(n\) consecutive terms in a period of the sequence. De Bruijn sequences have been widely studied because of their equivalence with Hamiltonian cycles in the de Bruijn graph. The degree of the shortest linear recurrence which generates the sequence \(s\) is called the linear complexity of \(s\). For \(p=2\), the linear complexity has been thoroughly investigated. The present paper extends this investigation to general finite fields, where both results and techniques vary considerably from those in the binary case. The basic goal of the paper is to determine as much as possible about the range of values of the linear complexity \(c\) of span \(n\) de Bruijn sequences. Both nonexistence results and families of examples are given. A sharp upper bound on \(c\) is obtained and significant evidence is obtained to show that a certain lower bound may be sharp. Many of the results are obtained with the help of a connection established between the theory of permutation polynomials and de Bruijn sequences of a given linear complexity.
- On the minimum linear complexity of de Bruijn sequences over non-prime finite fields
- Characterising the linear complexity of span 1 de Bruijn sequences over finite fields.
- Preliminary results on the minimal polynomial of modified de Bruijn sequences
- On the linear complexity profile of explicit nonlinear pseudorandom numbers.
- The minimal polynomials of modified de Bruijn sequences revisited
- Factor complexity and permutation complexity of the generalized Morse sequence
- On the \(k\)-error linear complexity of binary sequences derived from the discrete logarithm in finite fields
- On the Carlitz rank of permutations of \(\mathbb F_q\) and pseudorandom sequences
- Some notes on the linear complexity of Sidel'nikov-Lempel-Cohn-Eastman sequences
- Linear difference equations and periodic sequences over finite fields
- On the linear complexity profile of nonlinear congruential pseudorandom number generators of higher orders
- Additive character sums of polynomial quotients
- Construction of de Bruijn sequences of minimal complexity
- scientific article; zbMATH DE number 4042032 (Why is no real title available?)
- On the k-error linear complexity of binary sequences derived from polynomial quotients
- Expansion complexity and linear complexity of sequences over finite fields
- Linear complexity and expansion complexity of some number theoretic sequences
- Cyclotomic Mapping Permutation Polynomials over Finite Fields
- Roulette games and depths of words over finite commutative rings
- On the \(k\)-error linear complexity over \({\mathbb F}_p\) of Legendre and Sidelnikov sequences
- Minimal polynomials of the modified de Bruijn sequences
This page was built for publication: Permutation polynomials, de Bruijn sequences, and linear complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1924236)
