Improved long convolutions using generalized number theoretic and polynomial transforms
Generalized number theoretic and polynomial transforms can be used in the computation of a long convolution. This will reduce the computation complexity by a factor of two; it only requires fewer than 2 real multiplications, 45 real additions, and 10 data shifts per point for a typical 2048 array.