A Semi-Fast Fourier Transform Algorithm Over GF (2 to the mth power).
ILLINOIS UNIV AT URBANA-CHAMPAIGN COORDINATED SCIENCE LAB
Pagination or Media Count:
An algorithm which computes the Fourier Transform of a sequence of length n over GF 2 to the mth power using approximately 2nm multiplications and n squared nm additions is developed. The number of multiplications is thus considerably smaller than the n squared multiplications required for a direct evaluation, though the number of additions is somewhat larger. Unlike the Fast Fourier Transform, this method does not depend on the factors of n and can be used when n is not highly composite or is a prime. The bit complexity of the algorithm is analyzed in detail. Implementations and applications are briefly discussed. Author
- Theoretical Mathematics