伯利坎普－梅西算法

伯利坎普－梅西算法编辑

伯利坎普－梅西算法用来构造一个尽可能短的线性反馈移位寄存器来产生一个有限二元序列

s

N

{\displaystyle s^{N}}

，同时，该算法也给出了

s

N

{\displaystyle s^{N}}

的线性复杂度。该算法是一个多项式时间的迭代算法，以N长二元序列

a

0

,

a

1

,
.
.
.
,

a

N
−
1

{\displaystyle a_{0},a_{1},...,a_{N-1}}

为输入，输出产生给序列式的最短LFSR的特征多项式

f

N

{\displaystyle f_{N}}

及该LFSR的线性复杂度

L

{\displaystyle L}

。