文档介绍：该【现在密码学第14讲BM算法课件】是由【yzhqw888】上传分享，文档一共【12】页，该文档可以免费在线阅读，需要了解更多关于【现在密码学第14讲BM算法课件】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。B-M算法
1
线性移存器
(一)解方程法
已知序列a是由n级线性移存器产生的,且知a的连续2n位,可用解线性方程组的方法得到线性递推式。
例:设a=01111000是4级线性移存器产生的序列的8个连续信号,求该移存器的线性递推式。
2
解:产生a=01111000……的联系多项式
设其联结多项式f(x)=1+c1x+c2x2+c3x3+x4
线性递推式at=at-4+c3at-3+c2at-2+c1at-1
0+c3+c2+c1=1
1+c3+c2+c1=0
1+c3+c2+0=0
1+c3+0+0=0
解得:c3=1;c2=0;c1=0
故其联结多项式为1+x3+x4
3
1、概念简介
设是上的长度为N的序列,而
是上的多项式,c0=1.
如果f(x)是一个能产生a并且级数最小的线性移位寄存器的联系多项式,l是该移存器的级数,则称为序列a的线性综合解。
如果序列中的元素满足递推关系:
则称产生二元序列a。其中表示以f(x)为联系多项式的l级线性移位寄存器。
5
线性移位寄存器的综合问题可表述为:给定一个N长二元序列a,如何求出产生这一序列的最小级数的线性移位寄存器,即最短的线性移存器?
几点说明:
2、规定:0级线性移位寄存器是以f(x)=1为联系多项式的线性移位寄存器,且n长(n=1,2,…,N)全零序列,仅由0级线性移位寄存器产生。事实上,以f(x)=1为联系多项式的递归关系式是:ak=0,k=0,1,…,n-,这一规定是合理的。
1、联系多项式f(x)的次数l。因为产生a且级数最小的线性移位寄存器可能是退化的,在这种情况下f(x)的次数<l;并且此时f(x)中的cl=0,因此在联系多项式f(x)中c0=1,但不要求cl=1。
3、给定一个N长二元序列a,求能产生a并且级数最小的线性移位寄存器,就是求a的线性综合解。利用B-M算法可以有效的求出。
6
2、B-M算法要点
用归纳法求出一系列线性移位寄存器:
每一个都是产生序列a的前n项的最短线性移位寄存器,在的基础上构造相应的,使得是产生给定序列前n+1项的最短移存器,则最后得到的就是产生给定N长二元序列a的最短的线性移位寄存器。
7
3、B-M算法
1、取初始值:
2、设
均已求得,且
任意给定一个N长序列,按n归纳定义
记:再计算:
称dn为第n步差值。然后分两种情形讨论:
8
B-M算法流程
10
第2步,计算d4:d4=1·a4+1·a3+0·a2+1·a1=0,从而
第3步,计算d5:d5=1·a5+1·a4+0·a3+1·a2=0,从而
第4步,计算d6:d6=1·a6+1·a5+0·a4+1·a3=0,从而
这表明,即为产生所给序列一个周期的最短线性移位寄存器。
12