Fast algebraic convolution for prime power lengths

In this paper a new fast convolution algorithm is introduced. The concept of this new algorithm is fully algebraic. Therefore, no roundoff errors occur. The signal length N is a prime power N=pⁿ, p⩾2. Hence the paper generalizes the results of a previous paper (Minkwitz and Creutzburg, 1992) for power of 2 lengths. The cyclic convolution of signals of length N is interpreted as a multiplication of polynomials of degree N-1 modulo the polynomial X^N-1. The calculation in our new method is done in a finite field extension of the field Q of rational numbers. To minimize the number of operations, an extension field Q[ω] is chosen, with ω as a symbolic root of unity and deg[Q[ω]:Q]=(p-1/p[√N]*). Here, [ ]* and [ ]* denote the well-known CEILING and FLOOR functions, respectively, but rather a mapping to the next larger power of p. The method achieves an arithmetic cost of O (N log N·log log N) operations over Q, which is the same as that of the well-known algorithm by SCHONHAGE-STRASSEN. However, our algorithm avoids the much more complicated FERMAT arithmetic over integers and works for primes p≠2 as well, although it performs best with small p, preferably p=2 or 3