Permutation polynomials, de Bruijn sequences, and linear complexity (Q1924236)

From MaRDI portal
Revision as of 01:51, 20 March 2024 by Openalex240319060354 (talk | contribs) (Set OpenAlex properties.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Permutation polynomials, de Bruijn sequences, and linear complexity
scientific article

    Statements

    Permutation polynomials, de Bruijn sequences, and linear complexity (English)
    0 references
    0 references
    0 references
    0 references
    1 October 1997
    0 references
    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.
    0 references
    de Bruijn sequence
    0 references
    linear recurrence
    0 references
    finite fields
    0 references
    linear complexity
    0 references
    permutation polynomials
    0 references

    Identifiers