Permutation Polynomials, de Bruijn Sequences, and Linear Complexity
Permutation Polynomials, de Bruijn Sequences, and Linear Complexity
复制标题
DOI：
10.1006/jcta.1996.0088
复制
发表时间：
1996-10
期刊：
影响因子：
--
通讯作者：
S. Blackburn;T. Etzion;K. Paterson
中科院分区：
文献类型：
--
作者：
S. Blackburn;T. Etzion;K. Paterson
本文在置换多项式理论与给定线性复杂度的一般有限域上是否存在 de Bruijn 序列的问题之间建立了联系。该连接既用于构造一系列线性复杂度的跨度 1 de Bruijn 序列（排列），又用于证明任意跨度的不存在结果。建立了跨越有限域的 de Bruijn 序列的线性复杂度的上限和下限。给出的构造表明上限总是紧的，并且下限在许多情况下也是紧的。
The paper establishes a connection between the theory of permutation polynomials and the question of whether a de Bruijn sequence over a general finite field of a given linear complexity exists. The connection is 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 spannover a finite field are established. Constructions are given to show that the upper bound is always tight, and that the lower bound is also tight in many cases.