Computational Complexity of Fourier Transforms Over Finite Fields.
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1976
- Accession Number
- ADA034981
Entities
People
- D. V. Sarwate
- Franco P. Preparata
Organizations
- University of Illinois Urbana–Champaign