ISSN:
1432-0622
Keywords:
Keywords: Polynomial remainder sequence
;
Berlekamp-Massey algorithm
;
linear recurring sequence
;
factorial domain.
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
,
Technology
Notes:
Abstract. We present an extended polynomial remainder sequence algorithm XPRS for R[X] where R is a domain. From this we derive a Berlekamp-Massey algorithm BM/R over R. We show that if (α) is a linear recurring sequence in a factorial domain U, then the characteristic polynomials for (α) form a principal ideal which is generated by a primitive minimal polynomial. Moreover, this generator is monic when U[ [X] ] is factorial (for example, when U is Z or K[X 1 , X 2 , . . . , X n ] where K is a field). From XPRS we derive an algorithm MINPOL for determining the minimal polynomial of (α) when an upper bound on the degree of some characteristic polynomial and sufficiently many initial terms of (α) are known. We also show how to obtain a Berlekamp-Massey type minimal polynomial algorithm from BM/U and state BM – MINPOL/K explicitly with a further refinement. Examples are given for U = Z, GF(2) [Y ].
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s002000050008
Permalink
