The Berlekamp–Massey Algorithm over a Finite Commutative Ring

An algorithm for finding a monic polynomial of the least degree that generates a given sequence of length $\ell$ over a finite commutative ring $R$ with identity is presented. The complexity of the algorithm is $O(\ell_2)$ operations in $R$ as $\ell\to\infty$.