产生具有足够大线性复杂度的序列

本文着重对R.Rueppel关于“产生具有足够大线性复杂的序列”这篇论文进行了综述,并对其推论1作了进一步推广。通常,产生具有大的线性复杂度序列的一个方法,是将一个非线性函数f用于二元最长线性反馈移位寄存器(LFSR),当函数f表示为GF(2)上其变量乘积和的形式,则称f具有代数标准形式(ANY),在ANF中,f的非线性阶K是在一个乘积次中变量出现酌最高次数,众所周知,当非线性前馈函数f的阶为K时,则输出序列Z的线性复杂度的上限为其中~1L表示使用LFSR的长度,它表明了当函数f具有形式其中所有L个K阶项仅仅包含相邻的变量,且f’为级数不超过K-1次的任意函数,那么,产生的输出序列其线性复杂度的下限为此处L为素数,其证明利用了范德蒙到列式的性质。