Multisequence Synthesis over an Integral Domain

摘要

We first give an extension of F[x]-lattice basis reduction algorithm to the polynomial ring R[x] where F is a field and R an arbitrary integral domain. So a new algorithm is presented for synthesizing minimum length linear recurrence (or minimal polynomials) for the given multiple sequences over R. Its computational complexity is O(N~2) multiplications in R where N is the length of each sequence. A necessary and sufficient conditions for the uniqueness of minimal polynomials are given. The set of all minimal polynomials is also described.