Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Computational complexity of Fourier transforms over finite fields

Authors: F. P. Preparata and D. V. Sarwate
Journal: Math. Comp. 31 (1977), 740-751
MSC: Primary 68A20; Secondary 65DXX
MathSciNet review: 0436662
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we describe a method for computing the Discrete Fourier Transform (DFT) of a sequence of n elements over a finite field $ {\text{GF}}({p^m})$ with a number of bit operations $ O(nm\,\log (nm) \cdot P(q))$ where $ P(q)$ is the number of bit operations required to multiply two q-bit integers and $ q \cong 2\,{\log _2}n + 4\,{\log _2}m + 4\,{\log _2}p$. 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. Our algorithm is a combination of known and novel techniques. In particular, the finite-field DFT is at first converted into a finite field convolution; the latter is then implemented as a two-dimensional Fourier transform over the complex field. The key feature of the method is the fusion of these two basic operations into a single integrated procedure centered on the Fast Fourier Transform algorithm.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 68A20, 65DXX

Retrieve articles in all journals with MSC: 68A20, 65DXX

Additional Information

Keywords: Computational complexity, discrete Fourier transform, finite fields, convolution
Article copyright: © Copyright 1977 American Mathematical Society