Computational Complexity of Fourier Transforms Over Finite Fields.

摘要

This paper describes a method for computing the Discrete Fourier Transform (DFT) of a sequence of n elements over a finite field GF (p to the mth power) with a number of bit operations 0(nm log (nm). P(q)) where P(q) is the number of bit operations required to multiply two g-bit integers and g approx. = 2 log sub 2 + 4 log sub 2m + 4 log sub 2p. This method is uniformly applicable to all instances and its order of complexity is not inferior to that of methods whose success depends upon the existence of certain primes.