密码理论- UESTC 例下图是一个5级线性反馈移位寄存器,其初始状 态为(a121231a45)=(1,0,0,1,1) 输出序列 可求出输出序列为 001101001000010101110110001111100110 周期为31
密码理论---UESTC 例 下图是一个5级线性反馈移位寄存器，其初始状 态为（a1 ,a2 ,a3 ,a4 ,a5）=(1,0,0,1,1) 可求出输出序列为 1001101001000010101110110001111100110… 周期为31
密码理论- UESTC 总是假定c1C2,…,Cn中至少≠0,否则f(a1,a2…,an)=0。 总是假定cn=1 LFSR输出序列的性质:完全由其反馈函数决定 n级LFSR状态数:最多有2n个。 n级LFSR的状态周期:≤2n-1。 输出序列的周期=状态周期,≤2n-1。 选择合适的反馈函数可使序列的周期达到最大值 2n-1,周期达到最大值的序列称为m序列
密码理论---UESTC 总是假定c1 ,c2 ,…,cn中至少0，否则 f(a1 ,a2 ,…,an )≡0。 总是假定cn=1。 LFSR输出序列的性质：完全由其反馈函数决定。 n级LFSR状态数：最多有2 n个。 n级LFSR的状态周期： 2 n -1。 输出序列的周期=状态周期， 2 n -1。 选择合适的反馈函数可使序列的周期达到最大值 2n-1，周期达到最大值的序列称为m序列
密码理论- UESTC 23线性移位寄存器的一元多项式表示 设m级线性移位寄存器的输出序列满足递推关系 an+k=C1an+k1c2an+k2④…Cn2ak 用延迟算子D(Dak=ak)作为未定元,给出的反 馈多项式为:p(D)=1+c1D+,,+cn1Dm1+cnDn 这种递推关系可用一个一元高次多项式 p(x)=l+C x+. tcn-jx-tcnxn 表示,称这个多项式为LFSR的特征多项式或特征 多项式。 记2-1个非零序列的全体为G(p(x)
密码理论---UESTC 设n级线性移位寄存器的输出序列满足递推关系 an+k=c1an+k-1 c2an+k-2 … cnak (*) 用延迟算子 D(Dak=ak-1 ) 作为未定元，给出的反 馈多项式为： p(D)=1+c1D+…＋cn-1Dn-1＋cnDn 这种递推关系 可用一个一元高次多项式 p(x)=1+c1x+…＋cn-1x n-1＋cnx n 表示，称这个多项式为LFSR的特征多项式或特征 多项式。 2.3 线性移位寄存器的一元多项式表示 记2 n -1个非零序列的全体为G(p(x))
密码理论- UESTC 定义2.1给定序列{a},幂级数 ∑ax 称为该序列的生成函数
密码理论---UESTC 定义2.1 给定序列{ai }，幂级数 称为该序列的生成函数。 = − = 1 1 ( ) i i i A x a x
密码理论- UESTC 定理21设p(x)=1+c1x+…,+Cn1xm+cnx是GF(2)上的 多项式,G(p(x)中任一序列{a}的生成函数A(x)满 足 A(x)= xx p 其中0(x)=∑(cnx2ax2)
密码理论---UESTC 定理2.1 设p(x)=1+c1x+…+cn-1x n-1+cnx n是GF(2)上的 多项式，G(p(x))中任一序列{ai }的生成函数A(x)满 足： ( ) ( ) ( ) p x x A x = 1 1 1 ( ) ( ) n i n i j n i j i j x c x a x − − − = = 其中 =