On the minimum linear complexity of de Bruijn sequences over non-prime finite fields

DOI10.1006/JCTA.1998.2920MaRDI QIDQ1284473zbMATH OpenOpenAlexFDO

Authors Peter A. Hines

Publication date 25 January 2000

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jcta.1998.2920

zbMATH Keywords

de Bruijn sequencesfinite fieldlinear complexity

Mathematics Subject Classification ID

Recurrences (11B37) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Shift register sequences and sequences over finite alphabets in information and communication theory (94A55)

Review text

It is known that the maximum possible linear complexity of a span \(n\) de Bruijn sequence over the finite field \({\mathbb F}_{p^m}\) is \(p^{mn}-1\) and such a sequence may be constructed in a straightforward manner. The situation regarding the minimum linear complexity has proved more complex. \textit{S. R. Blackburn, T. Etzion} and \textit{K. G. Paterson} [J. Comb. Theory, Ser. A 76, No. 1, 55-82 (1996; Zbl 0871.11089)] showed that the linear complexity was never less than \(p^{mn-1}+n\) and for \(m\geq 2\) the lower bound is realized for some \(n\) including \(n=2\). They conjectured that for \(m\geq 2\) this lower bound is always realized. This conjecture is proved completely in the paper under reviewing. The proof is constructive. It seems that the better minimum for an odd prime field (i.e. \(m=1\)) is yet to be found. Some partial solution for this case was also given in the paper mentioned above.

Recommendations

• Construction of de Bruijn sequences of minimal complexity
• Linear complexity of de Bruijn sequences-old and new results
• Characterising the linear complexity of span 1 de Bruijn sequences over finite fields.
• The minimal polynomials of modified de Bruijn sequences revisited
• Permutation polynomials, de Bruijn sequences, and linear complexity

Cites work

• Characterising the linear complexity of span 1 de Bruijn sequences over finite fields.
• Construction of de Bruijn sequences of minimal complexity
• scientific article; zbMATH DE number 3882549 (Why is no real title available?)
• On the complexities of de-Bruijn sequences
• On the distribution of de Bruijn sequences of given complexity
• On the distribution of de Bruijn sequences of low complexity
• Perfect factors in the de Bruijn graph
• Permutation polynomials, de Bruijn sequences, and linear complexity

Cited in

(6)

• Minimum Eulerian circuits and minimum de Bruijn sequences
• Characterising the linear complexity of span 1 de Bruijn sequences over finite fields.
• Permutation polynomials, de Bruijn sequences, and linear complexity
• The minimal polynomials of modified de Bruijn sequences revisited
• Construction of de Bruijn sequences of minimal complexity
• Linear complexity of de Bruijn sequences-old and new results

This page was built for publication: On the minimum linear complexity of de Bruijn sequences over non-prime finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1284473)