The Berlekamp–Massey algorithm over finite rings, modules and bimodules

We give an algorithm for finding a monic polynomial of the least degree that generates a given sequence $u(0,l-1)$ of length $l$ with complexity $O(l^2)$ operations as $l\to\infty$. We consider the sequences $u(0,l-1)$ over a finite ring $R$ with identity, over a finite module $_R M$, or over finite bimodule $_A M_B$, where $A$ and $B$ are finite rings with identities.