文档介绍：线性移位寄存器
量子密码研究室
王滨
2005年3月29日
1
移位寄存器序列的三种表示方法:
线性递推式(一元多项式):
at+n=c1at+n-1+c2at+n-2+…+cnat ,t>=0
联结多项式:
f(x)=1+c1x+c2x2+…+cnxn
状态转移矩阵:
满足:st+1=stTf
称st=(at,at+1,at+2,…,at+n-1)为n维状态
2
实例(画出移存器的逻辑框图,写出相应的线性
递推式)
多项式
答案:
线性递推式: at=at-4+at-3+at-2
x1
x2
x3
x4
3
非退化的移位寄存器
若反馈函数形如:
,其中,则称其为线性反馈寄存器;否则称其为非线性反馈移为寄存器。
其中,若我们说该寄存器是退化的,否则是非退化的。
4
移位寄存器序列空间
符号说明:G(f)表示以f(x)为联结多项式的n级线性移位寄存器序列构成的空间
定理1:G(f)是GF(q)上的一个n维线性空间。
证明:只需证明G(f)中的任意两个序列的任意线性组合也属于G(f)即可。即证:

特例:当q=2时,G(f)中任意两个序列之和仍然属于G(f)。
5
(不)可约多项式
定义:若存在g(x),h(x),使得f(x)=g(x)h(x),则称f(x)是可约多项式;否则,称其为不可约多项式。
(不)可约多项式
6
定理2:若f(x)|h(x),则G(f) G(h).
例1:联结多项式为
f(x)=x4+x3+x+1=(x+1)2(x2+x+1)
线性递推式:at=at-4+at-3+at-1
输出序列:000111//000111//……周期为6
011//011//……周期为3
001//001//……周期为3
01//01//……周期为2
111111….. 周期为1
000000……周期为1
7
极小多项式
定义:对于一条移位寄存器序列a,称其联结多项式中次数最低的多项式为a的极小多项式。
定义:满足f(x)|1-xr 的最小正整数r为f(x)的周期,记为p(f(x)),简记为p(f)。
例子:x4+x3+x2+x+1的周期为5
(x4+x3+x2+x+1)(x+1)=x5+1
8
序列和周期
一般地,一个移存器序列表示为:
对于序列,若存在整数p使得对任意正整数k有成立,称满足该式的最小正整数p为序列的周期。
r级线性反馈移存器的最长周期: ,能达到最长周期的线性移存器序列称为m序列。
在密码学中,我们希望参与变换的序列周期越长越好,因此对线性反馈移存器我们更感兴趣的是能达到最长周期的序列,即m序列。
9
本原多项式
若n次多项式f(x)是不可约多项式且p(f)=qn-1,则称f(x)是GF(q)上的本原多项式。
以本原多项式为连接多项式产生的非零序列均是m序列。
10