No label defined (Q4501006)

The Berlekamp-Massey algorithm over an arbitrary finite ring with identity \(e\) is presented. Let \(R\) be a finite ring with identity \(e\). A polynomial \(f(x)=x^s-c_{s-1}x^{s-1}-\dots-c_1x-c_0 \in R[x]\) generates (from the left) a sequence \(u(0,\dots,l-1)=\bigl(u(0),u(1),\dots,u(l-1)\bigr)\in R^l\) if \(s\geq l\) or \(s< l\) and \[ u(i+s)=c_{s-1}u(i+s-1)+\dots +c_1u(i+1)+c_0u(i), \quad i=1,\dots,l-s-1. \] A monic polynomial of the smallest degree which generates \(u(0,\dots,l-1)\) is called its (left) minimal polynomial. The Berlekamp-Massey algorithm finds a minimal polynomial of a sequence of operations of \(R\) which has length \(l\) and complexity \(O(l^2)\). Many versions are available of the Berlekamp-Massey algorithm over fields as well as its generalization for some commutative rings. The complexity (the number of operations of the ring \(R\)) of the algorithm proposed is at most \[ (2M^2+10M)l^2 + O(l), \quad l\to \infty, \] where \(M\) is the number of classes of left-associated nonzero elements of \(R\); in particular, \(M<|R|\). For the entire collection see [Zbl 0918.00043].