屈　哲　陈克非

1(上海交通大学计算机科学与工程系　上海 200240)2(杭州师范大学理学院　浙江 杭州 310036)3(保密通信重点实验室　四川 成都 610041)



寻找Span n序列的方法的改进

屈哲1,3陈克非2,3

1(上海交通大学计算机科学与工程系上海 200240)2(杭州师范大学理学院浙江 杭州 310036)3(保密通信重点实验室四川 成都 610041)

de Bruijn序列是一个周期为2n的0、1序列，去掉n阶de Bruijn序列中连续的n个0中的一个得到一个周期为2n-1的序列，称为span n序列。一个n阶de Bruijn序列的线性复杂度在2n-1+n和2n-1之间，然而对应的span n序列的线性复杂度可能降为n。所以span n序列的线性复杂度成为了衡量一个de Bruijn序列好坏的重要标准，因此研究生成高线性复杂度的span n序列的方法是非常有意义的。研究文献[6]中提出的基于特殊函数和非线性反馈移位寄存器寻找span n序列的方法，发现span n序列与参数t的无关性，并基于此提出了几种改进算法。对各种算法进行横向比较，并指出了每种算法的局限和优点，以及今后可能的改进。

非线性反馈移位寄存器de Bruijn序列span n序列

0　引　言

近些年，在伪随机序列生成器。流密码和一些轻量级的分组密码等领域，非线性反馈移位寄存器NLFSR(Nonlinear Feedback Shift Register)受到了越来越多的关注。基于非线性反馈移位寄存器的密码在一些需要高效硬件实现和高吞吐量等受限制的环境下表现出良好的实用价值，发挥着重要的作用。

在流密码中，加密使用的是将明文和密钥流以比特为单位进行那个异或操作来产生密文。流密码要求密钥流是一个随机的比特流，而NLFSR恰好满足此要求。……