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

DOI:
https://doi.org/10.1090/S0025-5718-1977-0436662-8

MathSciNet review:
0436662

Full-text PDF

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 with a number of bit operations where is the number of bit operations required to multiply two *q*-bit integers and . 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.

**[1]**E. R. BERLEKAMP,*Algebraic Coding Theory*, McGraw-Hill, New York, 1968. MR**38**#6873. MR**0238597 (38:6873)****[2]**F. J. MacWILLIAMS & N. J. A. SLOANE,*Theory of Error-Correcting Codes*, American Elsevier, New York. (To appear.)**[3]**J. M. POLLARD, "The fast Fourier transform in a finite field,"*Math. Comp.*, v. 25, 1971, pp. 365-374. MR**46**#1120. MR**0301966 (46:1120)****[4]**A. V. AHO, J. E. HOPCROFT & J. D. ULLMAN,*The Design and Analysis of Computer Algorithms*, Addison-Wesley, Reading, Mass., 1974. MR**0413592 (54:1706)****[5]**A BORODIN & I. MUNRO,*The Computational Complexity of Algebraic and Numerical Problems*, American Elsevier, New York, 1975. MR**0468309 (57:8145)****[6]**C. M. RADER, "Discrete convolutions via Mersenne transforms,"*IEEE Trans. Computers*, v. C-21, No. 12, 1972, pp. 1269-1273. MR**0438672 (55:11580)****[7]**R. C. AGARWAL & C. S. BURRUS, "Number theoretic transforms to implement fast digital convolution,"*Proc. IEEE*, v. 63, No. 4, 1975, pp. 550-560. MR**0451632 (56:9914)****[8]**I. S. REED & T. K. TRUONG, "The use of finite fields to compute convolutions,"*IEEE Trans. Information Theory*, v. IT-21, No. 2, 1975, pp. 208-213. MR**0406677 (53:10463)****[9]**A. SCHÖNHAGE & V. STRASSEN, "Schnelle Multiplikation grosser Zahlen,"*Computing*, v. 7, 1971, pp. 281-292. MR**45**#1431. MR**0292344 (45:1431)****[10]**L. I. BLUESTEIN, "A linear filtering approach to the computation of discrete Fourier transform,"*IEEE Trans. Audio & Electroacoustics*, v. AU-18, 1970, pp. 451-455.**[11]**C. M. RADER, "Discrete Fourier transforms when the number of data samples is prime,"*Proc. IEEE*(Letters), v. 56, No. 6, 1968, pp. 1107-1108.**[12]**J. W. COOLEY & J. W. TUKEY, "An algorithm for the machine calculation of complex Fourier series,"*Math. Comp.*, v. 19, 1965, pp. 297-301. MR**31**#2843. MR**0178586 (31:2843)****[13]**S. W. GOLOMB, "Properties of the sequence "*Math. Comp.*, v. 30, 1976, pp. 657-663.**[14]**D. E. KNUTH,*The Art of Computer Programming*. Vol. 2:*Seminumerical Algorithms*, Addison-Wesley, Reading, Mass., 1971. MR**44**#3531. MR**633878 (83i:68003)****[15]**R. C. AGARWAL & C. S. BURRUS, "Fast one-dimensional digital convolution by multidimensional techniques,"*IEEE Trans. Acoustics, Speech and Signal Processing*, v. ASSP-22, No. 1, 1974, pp. 1-10. MR**0401340 (53:5169)**

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

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

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1977-0436662-8

Keywords:
Computational complexity,
discrete Fourier transform,
finite fields,
convolution

Article copyright:
© Copyright 1977
American Mathematical Society