A Semi-Fast Fourier Transform Algorithm Over GF (2 to the mth power).

摘要

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)