移位寄存器序列理论

第1章线性反馈移位寄存器序列 这一章介绍线性反馈移位寄存器序列的基本理论，内容涉及特征多项式、极小多项式、周期、序列簇的分解和乘积、序列的表示、m-序列、序列的综合算法、序列的线性复杂度等。 1.1线性反馈移位寄存器序列的描述 反馈移位寄存器是生成伪随机序列的重要模型，是许多密钥序列生成器的重要部件。 图1.1F2上n级反馈移位寄存器 首先引入反馈移位寄存器的模型，设n是正整数，二元域F 上n级反馈移位寄存器如图1. 所示，其中x0，x1， ，xn.1是n个比特寄存器，g(x0，x1， ，xn.1)是n元布尔函数，称为该反馈移位寄存器的反馈函数。 反馈移位寄存器输出序列的方式如下。 首先在n个寄存器中输入初始值x0=a0， ，xn. =an.1(a0， ，an. ∈F2)，加载一次移位脉冲后，n 个寄存器中的比特依次左移，*左边的寄存器x 的比特移出，并作为这一时刻的输出比特，同时，将g(a0，a1， ，an.1)反馈到*右边的寄存器xn.1，即设第0时刻(x0，x1， ，xn.2， xn.1)=(a0，a1， ，an.2，an.1)，则第1时刻(x0，x1， ，xn.2，xn.1)=(a1， a2， ，an.1，an)，其中， an =g(a0，a1， ，an.1)∈F 通过连续加载移位脉冲，反馈移位寄存器输出F 上的序列a=(a0，a1，a2， )（即寄存器x 的输出序列）。该序列满足递归式： ak+n =g(ak， ，ak+n.1)，k=0，1，2， (1.1) 称a为n级反馈移位寄存器序列，(ak， ，ak+n.1)为k时刻的状态，特别地，称(a0， a1， ，an.1)为该反馈移位寄存器的初始状态。 当g(x0， ，xn.1)=c0x0+c1x1+ +cn.1xn.1(ci ∈F2(i =0，1，2， ，n.1))， 即g(x0， ，xn.1)是线性函数时，称图1. 给定的反馈移位寄存器为线性反馈移位寄存器(LinearFeedbackShiftRegister，LFSR)，所产生的序列称为线性反馈移位寄存器序列，简称LFSR序列。此时所产生的F 上的序列满足线性递归式： ak+n =c0ak +c1ak+ + +cn.1ak+n.1，k=0，1，2， (1.2) 也称序列a=(a0，a1，a2， )为F 上的n级线性递归序列。 注1.1线性递归序列是LFSR序列的数学描述，以后在称谓上就用LFSR序列。 在这一章中，主要介绍二元域F 上线性反馈移位寄存器序列（线性递归序列）的基本 理论。记F∞2={a=(a0，a1，a2， )|ai∈F2} 为域F 上所有无限序列组成的集合。 定义1.1设a=(a0，a1，a2， )∈F∞2，若a满足线性递归式(1.2)，则称f(x)=xn +cn.1xn. + +c 为a的一个特征多项式，也称序列a以f(x)为特征多项式。记G(f(x))为F∞2中以f(x)为特征多项式的序列全体。 给定F 上的n次多项式f(x)，设a=(a0，a1，a2， )∈G(f(x))。显然，序列a由前n比特a0，a1， ，an. 唯一确定，从而|G(f(x))|=2n。 从以上的分析可以看出，给定f(x)∈F2[x]，其中degf(x).1，就相当于给定了一个线性反馈移位寄存器，而一个线性反馈移位寄存器随着初始状态的不同，输出的序列也不同。G(f(x))就是以f(x)为特征多项式的线性反馈移位寄存器所能产生的序列的全体。 注1.2利用特征多项式刻画LFSR序列有利于运用数学（特别是代数学）对LFSR序列进行深入研究。因此，以后主要利用特征多项式来研究序列，而线性反馈移位寄存器用于形象地说明序列是如何输出的。 除了线性反馈移位寄存器和线性递归式，还可以用矩阵刻画序列的生成。 设f(x)=xn+cn.1xn. + +c ∈F2[x]，a=(a0，a1，a2， )∈G(f(x))，令 则(a1， ，an)=(a0， ，an.1)A。一般地，有 (ak， ，ak+n.1)=(a0， ，an.1)Ak，k=0，1，2， 称A是G(f(x))（或f(x)所确定的线性反馈移位寄存器）的状态转移矩阵。 序列的基本运算定义如下。 设a=(a0，a1，a2， )，b=(b0，b1，b2， )∈F∞2，c ∈F2，定义序列的加法和数 乘为 定义左移运算如下： 一般地，有并且定义 根据上面的定义，多项式对序列的作用有如下基本性质。 引理1.1设f(x)，g(x)∈F2[x]，a，b∈F∞2，c ∈F2，则有 (f(x)+g(x))a=f(x)a+g(x)a f(x)(a+b)=f(x)a+f(x)b f(x)(ca)=c(f(x)a) 证明是显然的。 对于f(x)∈F2[x]，degf(x).1，a∈F∞2，记0=(0，0， )是全0序列，根据上述序列运算的定义，有 a∈G(f(x))当且仅当f(x)a=0 即 G(f(x))={a∈F∞ |f(x)a=0} 注1.3当f(x)=0或1时，以f(x)为特征多项式的序列无法按线性递归方式进行定义，但按多项式作用于序列的定义，可以认为：以f(x)=1为特征多项式的序列只有全 序列0，而F∞2中的每一个序列都以f(x)=0为特征多项式，从而可以定义 G(1)def ==={0}，G(0)def ===F∞ 这样，对于f(x)∈F2[x]，a∈F∞2，有a∈G(f(x))当且仅当f(x)a=0，即 G(f(x))={a∈F∞ |f(x)a=0} G(f(x))是F 上的向量空间，并且有下面的维数结论。 定理1.1设0.=f(x)∈F2[x]，degf(x)=n，则G(f(x))是F 上的n维向量空间。 证明当n=0时，即f(x)=1时，结论显然成立。 下面设n.1。对于任意的a，b∈G(f(x))和c∈F2，由引理1.1可得 f(x)(a+b)=f(x)a+f(x)b=0，f(x)(ca)=c(f(x)a)=0 所以a+b∈G(f(x))，ca∈G(f(x))，G(f(x))是F 上的向量空间。 又因为|G(f(x))| =2n，所以G(f(x))是F 上的n维向量空间。 本书主要讨论二元序列，即F 上的序列。在讨论F 上的序列的过程中，会涉及一般有限域上的序列。为此，将线性递归序列及相关概念推广到一般有限域上。 定义1.2设Fq是q元有限域，c0， ，cn.1∈Fq，若Fq上的序列a=(a0，a1，a2， )满足 an+k =c0ak +c1ak+ + +cn.1ak+n.1，k=0，1，2， 则称a是Fq上的n级线性递归序列，并称f(x)=xn.(cn.1xn. + +c0)是序列a的一个特征多项式。同样，记 F∞q={a=(a0，a1，a2， )|ai∈Fq} 为Fq上所有无限序列组成的集合，并记G(f(x))为F∞q中以f(x)为特征多项式的序列全 体，则有 G(f(x))={a∈F∞q |f(x)a=0} 如果不做特别说明，所讨论的线性递归序列或LFSR序列是指二元域F2上的序列。 1.2极小多项式与周期 设a=(a0，a1， )∈F∞2，因为对于任意非负整数i和j，有xi+ja=xi(xja)=xj(xia)所以对于任意f(x)∈F2[x]，有 (xif(x))a=xi(f(x)a)=f(x)(xia) 从而对于任意f(x)，g(x)∈F2[x]，有(f(x)g(x))a=f(x)(g(x)a)=g(x)(f(x)a) 即有引理1.2。 引理1.2设f(x)，g(x)∈F2[x]，a∈F∞2，则有 (f(x)g(x))a=f(x)(g(x)a)=g(x)(f(x)a) 设序列a∈F∞2以f(x)为特征多项式，即f(x)a=0，则对于任意0.=g(x)∈F2[x]，由引理1.2可知，g(x)f(x)也是a的特征多项式，所以序列a的特征多项式不唯一。 对于a∈F∞2，定义 由引理1.1和引理1.2，得定理1.2。 定理1.2设a是LFSR序列，则A(a)是F2[x] 的一个理想，即若f(x)，g(x)∈A(a)， h(x)∈F2[x]，则f(x)+g(x)∈A(a)，h(x)f(x)∈A(a)。 注1.4称A(a)为序列a的特征多项式理想。 显然A(0)是单位理想，即A(0)=F2[x]。 定义1.3设a是LFSR序列，称a的次数*小的特征多项式为a的极小多项式，并 称a的极小多项式次数为a的线性复杂度，记为LC(a)。 注1.5序列的极小多项式为f(x)=1；而序列1def (1，1，1， )的极小多项式为x.1；而非0LFSR 序列的极小多项式次数.1。 序列的极小多项式与特征多项式有下面的关系。 定理1.3设a∈F∞2 是LFSR序列，则a的极小多项式是唯一的。进一步，设m(x)是a的极小多项式，f(x)是a的一个特征多项式，则m(x)|f(x)。