首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >Berlekamp-Massey算法中的偏差$δ$

问Berlekamp-Massey算法中的偏差$δ$
EN

Cryptography用户
提问于 2021-07-31 17:23:33
回答 2查看 141关注 0票数 2

我有一个关于Berlekamp-Massey算法的问题。有人能引导我理解这个算法的思想/直觉吗?

根据维基百科中的解释,在每一次迭代中,算法都试图计算出差异δ。

如果是δ≠0,该算法将使用更新多项式B(x)更新错误定位器多项式。但是,在这一点上,我知道所得到的误差定位器多项式将使当前迭代中的δ变为零。但是,在以前的迭代中,所有的δ如何?很难想象该算法实际上生成了所有以前的δ=0。

EN

回答 2

Cryptography用户

发布于 2021-07-31 21:32:58

实际上,BMA是一种递归算法,差异d_{n+1}=\hat{s}_{n+1}-s_{n+1}是

  • 由BMA根据序列C^{\{n\}}确定的当前多项式(s_0,\cdots,s_n)作为下一个符号\hat{s}_{n+1}预测了什么,以及
  • 实际符号s_{n+1}。

如果有必要,这是用来更新多项式的。通过归纳,所有差异都为零。

票数 1
EN

Cryptography用户

发布于 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保证生成到目前为止检查的所有序列,而不会在生成过程中出现任何差异。

票数 1
EN
页面原文内容由Cryptography提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://crypto.stackexchange.com/questions/93341

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档