Computational Complexity of Fourier Transforms Over Finite Fields.
ILLINOIS UNIV AT URBANA-CHAMPAIGN COORDINATED SCIENCE LAB
Pagination or Media Count:
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 0nm log nm. Pq where Pq 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.
- Theoretical Mathematics