我有一个关于Berlekamp-Massey算法的问题。有人能引导我理解这个算法的思想/直觉吗?
根据维基百科中的解释,在每一次迭代中,算法都试图计算出差异δ。
如果是δ≠0,该算法将使用更新多项式B(x)更新错误定位器多项式。但是,在这一点上,我知道所得到的误差定位器多项式将使当前迭代中的δ变为零。但是,在以前的迭代中,所有的δ如何?很难想象该算法实际上生成了所有以前的δ=0。
发布于 2021-07-31 21:32:58
实际上,BMA是一种递归算法,差异d_{n+1}=\hat{s}_{n+1}-s_{n+1}是
如果有必要,这是用来更新多项式的。通过归纳,所有差异都为零。
发布于 2021-12-29 20:16:31
Berlekamp-Massey算法是LFSR综合的一个过程。查找将产生给定序列s_0, s_1, s_2, \cdots的最短LFSR。该算法是迭代的(不是递归的,因为它不调用自己),因为它每次只检查一个符号,直到处理完整个给定的序列。在i-th迭代结束时,该算法研究了s_0, s_1, \cdots, s_{i-1} ( s_i, s_{i+1}, \cdots的检验尚未到来),并合成了生成s_0, s_1, \cdots, s_{i-1}的最短的LFSR。然后,在(i+1)-th迭代开始时,该算法通过计算刚刚合成的LFSR的下一个输出\hat{s}_i,并将其与我们希望生成的s_i (即给定的s_i )进行比较,确定它是否将由它找到的LFSR生成。这种差异称为差异\delta_i,如果\delta_i碰巧为非零,则更新先前合成的LFSR,以便更新的LFSR将计算s_0, s_1, \cdots, s_{i-1}, {\mathbf s_i} (重点添加)。此更新可能会增加LFSR长度,还会更改反馈龙头,或者只更改反馈水龙头。可以证明,如果迭代导致LFSR长度的增加和taps的改变,那么在下一次迭代中,只有反馈抽头可能改变,LFSR不能增加长度。
简而言之,没有必要担心以前的差异会发生什么;目前的LFSR保证生成到目前为止检查的所有序列,而不会在生成过程中出现任何差异。
https://crypto.stackexchange.com/questions/93341
复制相似问题