# Accession Number:

## ADA034982

# Title:

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

# Descriptive Note:

## Technical rept.,

# Corporate Author:

## ILLINOIS UNIV AT URBANA-CHAMPAIGN COORDINATED SCIENCE LAB

# Personal Author(s):

# Report Date:

## 1976-09-01

# Pagination or Media Count:

## 26.0

# Abstract:

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

# Descriptors:

# Subject Categories:

- Theoretical Mathematics