Berlekamp-Massey算法

Berlekamp-Massey算法用于在$O(n^2)$的时间内求解数列的递推式。形式化地讲,给定$a_i(i=0,1,2,3…n-1)$,求一组$b_j(j=0,1,2,3…m)$,满足:

其中或许会有条件限制$m$最小。

构造

考虑现在我们已经有了一个递推式$[f]$且满足了前$k$项