Permutation polynomials, de Bruijn sequences, and linear complexity
type: Item
instance of: scholarly article
title: Permutation polynomials, de Bruijn sequences, and linear complexity
zbMATH Open document ID: 0871.11089
author: Simon R. Blackburn
author: Tuvi Etzion
author: Kenneth G. Paterson
published in: Journal of Combinatorial Theory. Series A
publication date: 1997-10-01T00:00:00Z
review text: 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.
reviewed by: Stanley E. Payne
Mathematics Subject Classification ID: 11T06
Mathematics Subject Classification ID: 11B37
zbMATH DE Number: 934991
zbMATH Keywords: de Bruijn sequence
zbMATH Keywords: linear recurrence
zbMATH Keywords: finite fields
zbMATH Keywords: linear complexity
zbMATH Keywords: permutation polynomials
MaRDI profile type: Publication
full work available at URL: jcta.1996.0088
OpenAlex ID: W2037656036
DOI: 10.1006/JCTA.1996.0088
description: scientific article; zbMATH DE number 934991