文档介绍：B-M 算法
量子密码研究室
王滨
2005年4月6日
上节内容复****br/>移位寄存器序列的三种表示方法：
线性递推式（一元多项式）：
at+n=c1at+n-1+c2at+n-2+…+cnat ,t>=0
联结多项式：
2 n
f(x)=1+c1x+c2x +…+cnx
状态转移矩阵：
满足：st+1=stTf
称st=(at,at+1,at+2,…,at+n-1)为n维状态
2
几个概念
非退化的移位寄存器
(不)可约多项式
极小多项式
序列和周期
本原多项式
m序列
1游程、0游程
m序列的游程分布规律
3
线性移存器
（一）解方程法
已知序列a是由n级线性移存器产生的，且知a
的连续2n位，可用解线性方程组的方法得到线性递
推式。
例：设a=01111000是4级线性移存器产生的序列
的8个连续信号，求该移存器的线性递推式。
4
解：产生 a=01111000……的联结
多项式
2 3 4
设其联结多项式f(x)=1+c1x+c2x +c3x +x
线性递推式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
5
（二）、B-M迭代算法
根据密码学的需要，对线性反馈移位寄存器
(LFSR)主要考虑下面两个问题：
（1）如何利用级数尽可能短的LFSR产生周期大、随
机性能良好的序列，即固定级数时，什么样的移存器
序列周期最长。这是从密钥生成角度考虑，用最小的代价
产生尽可能好的、参与密码变换的序列。
（2）当已知一个长为N序列a时，如何构造一个级
数尽可能小的LFSR来产生它。这是从密码分析角度来考
虑，要想用线性方法重构密钥序列所必须付出的最小代价。
这个问题可通过B-M算法来解决。
6
1、概念简介
设 = 0. 1 " aaaa N −1),,,( 是F2 上的长度为N的序列，而
2 l 是 上的多项式，c =1.
)( 210 "++++= l xcxcxccxf F2 0
如果序列中的元素满足递推关系：
= kk − + k −2211 +"+ −lkl = + " Nllkacacaca − )2(1,,1,,
则称),( lxf 产生二元序列a。其中),( lxf 表示以f(x)为反馈
多项式的l级线性移位寄存器。
如果f(x)是一个能产生a并且级数最小的线性移位寄存器的
反馈多项式，l是该移存器的级数，则称),( lxf 为序列a的
线性综合解。
7
线性移位寄存器的综合问题可表述为：给定一个N长
二元序列a，如何求出产生这一序列的最小级数的线性移
位寄存器，即最短的线性移存器？
几点说明：
1、反馈多项式f(x)的次数≤l。因为产生a且级数最小的线性
移位寄存器可能是退化的，在这种情况下 f(x)的次数<l；并且此
时 f(x)中的cl=0，因此在反馈多项式f(x)中c0=1，但不要求cl=1。
2、规定：0级线性移位寄存器是以f(x)=1为反馈多项式的
线性移位寄存器，且n长(n=1, 2, …, N)全零序列，仅由0级线性
移位寄存器产生。事实上，以f(x)=1