Algorithms and the multiplicative complexity of the reduction amodulo arbitrary polynomial, generalized K_N-convolution andfast Vandermonde transform

摘要

This paper proves that the number of multiplications required forcalculating the product of two polynomial modulo and arbitrarypolynomial q(z) (or generalized K_N-convolution), whosecoefficients do not belong to the field of constants, is three timeshigher than the estimate for the case when the coefficients do belong tothe field of constants. The existence of a fast Vandermonde transform(FVT) algorithm with the multiplicative complexity (O4NlogN) is shown.The new fast algorithms have applications in filtering and interpolationof digital signal and images