PERMUTATION POLYNOMIALS, DE-BRUIJN SEQUENCES, AND LINEAR COMPLEXITY

The paper establishes a connection between the theory of permutation p olynomials and the question of whether a de Bruijn sequence over a gen eral finite held of a given linear complexity exists. The connection i s used both to construct span 1 de Bruijn sequences (permutations) of a range of linear complexities and to prove non-existence results for arbitrary spans. Upper and lower bounds for the linear complexity of a de Bruijn sequence of span n over a finite field are established. Con structions are given to show that the upper bound is always tight, and that the lower bound is also tight in many cases. (C) 1996 Academic P ress, Inc.