Computational complexity of generalized $K_N$-convolutions and the fast Vandermonde transform algorithm

A lemma on the minimum multiplicative complexity of the reduction operation for polynomials whose coefficients are not in the field of constants in Winograd's sense is proved. The lemma is used to prove theorems on the minimum number of multiplications necessary to compute the generalized $K_N$-convolution and on the existence of a fast Vandermonde transform (FVT) algorithm. An $O(2N\log_2^2N)$ $N$-point algorithm is synthesized.