FUNDAMENTALNAYA I PRIKLADNAYA MATEMATIKA

(FUNDAMENTAL AND APPLIED MATHEMATICS)

1999, VOLUME 5, NUMBER 4, PAGES 1061-1101

The Berlekamp--Massey algorithm over commutative Artinian principal ideal rings

V. L. Kurakin

Abstract

View as HTML     View as gif image    View as LaTeX source

The algorithm constructing the monic polynomial of minimal degree which generates the given sequense of the length $l$ over commutative Artinian principal ideal ring $R$ is presented. The complexity of the algorithm is $O(l2n)$ operations of $R$, where $n$ is the index of nilpotency of the radical of $R$. The algorithm is applied for construction of the canonical system of generators of the ideal of all polynomials annihilating the given linear recurring sequence over $R$.

All articles are published in Russian.

Location: http://mech.math.msu.su/~fpm/eng/99/994/99407h.htm
Last modified: December 9, 1999