New techniques for the computation of linear recurrence coefficients (Q1971066)

The paper shows algorithms to compute the \(n\)th coefficients of a linear recurrence or, equivalently, the coefficients of a polynomial expressed via the power sums of its zeros. The problem is equivalent to the key equation for decoding BCH error-correcting codes. It has applications in sparse multivariate polynomial interpolation and computation with sparse matrices over finite fields. Previous algorithms for the problem provided an upper bound of \(O(\mu (n) \log n)\), where \(\mu (n)= O(n \log n \log \log n)\) is the bound for multiplying a pair of polynomials modulo \(x^n\). For \(c\) the characteristic of the field of the allowed constants, the algorithms presented in the paper have upper bound \(O(\mu (n))\), if \(c=0\) or \(c> n\). For \(0 < c \leq n\), the Las Vegas type randomization algorithm results in an upper bound of \(O(\mu (n) + \mu (n/c) \log (n/c))\) field operations.