An iterative algorithm for parametrization of shortest length linear shift registers over finite chain rings

The construction of shortest feedback shift registers for a finite sequence \(S_1,\ldots ,S_N\) is considered over finite chain rings, such as \({\mathbb Z}_{p^r}\). A novel algorithm is presented that yields a parametrization of all shortest feedback shift registers for the sequence of numbers \(S_1,\ldots ,S_N\), thus solving an open problem in the literature. The algorithm iteratively processes each number, starting with \(S_1\), and constructs at each step a particular type of minimal basis. The construction involves a simple update rule at each step which leads to computational efficiency. It is shown that the algorithm simultaneously computes a similar parametrization for the reverse sequence \(S_N,\ldots ,S_1\). The complexity order of the algorithm is shown to be \(O(r N^2)\).