New techniques for the computation of linear recurrence coefficients

The n coefficients of a fixed linear recurrence can be expressed through its m less than or equal to 2n terms or, equivalently, the coefficients of a polynomial of a degree n can be expressed via the power sums of its zeros-by means of a polynomial equation known as the key equation for decoding the BCH error-correcting codes. The same problem arises in sparse multivariate polynomial interpolation and in various fundamental computations with sparse matrices in finite fields. Berlekamp's algorithm of 1968 solves the key equation by using order of n(2) operations in a fixed field. Several algorithms of 1975-1980 rely on the extended Euclidean algorithm and computing Pade approximation, which yields a solution in O(n (log n)(2) log log n) operations, though a considerable overhead constant is hidden in the "O" notation. We show algorithms (depending on the characteristic c of the ground field of the allowed constants) that simplify the solution and lead to further improvements of the latter bound, by factors ranging from order of log n, for c = 0 and c > n (in which case the overhead constant drops dramatically), to order of min (c,log n), for 2 less than or equal to c less than or equal to n; the algorithms use Las Vegas type randomization in the case of 2 < c less than or equal to n. (C) 2000 Academic Press.