On the multiplicative complexity of the Discrete Fourier Transform

AbstractMost results in multiplicative complexity assume that the functions to be computed are in the field of constants extended by indeterminates, that is, the variables satisfy no algebraic relation. In this paper we extend some of the known results to the case that some of the variables do satisfy some algebraic relations. We then apply these results to obtaining a lower bound on the multiplicative complexity of the Discrete Fourier Transform. In the special case of computing the Discrete Fourier Transform of a prime number of points, the lower bound is actually attainable