Accession Number:

ADA034981

Title:

Computational Complexity of Fourier Transforms Over Finite Fields.

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:

27.0

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 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.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE