Algorithms and the multiplicative complexity of the reduction a modulo arbitrary polynomial, generalized K/sub N/-convolution and fast Vandermonde transform

This paper proves that the number of multiplications required for calculating the product of two polynomial modulo and arbitrary polynomial q(z) (or generalized K/sub N/-convolution), whose coefficients do not belong to the field of constants, is three times higher than the estimate for the case when the coefficients do belong to the 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 interpolation of digital signal and images.