Computational complexity of Fourier transforms over finite fields
Authors:
F. P. Preparata and D. V. Sarwate
Journal:
Math. Comp. 31 (1977), 740751
MSC:
Primary 68A20; Secondary 65DXX
MathSciNet review:
0436662
Fulltext 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 with a number of bit operations where is the number of bit operations required to multiply two qbit 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 finitefield DFT is at first converted into a finite field convolution; the latter is then implemented as a twodimensional 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]
Elwyn
R. Berlekamp, Algebraic coding theory, McGrawHill Book Co.,
New YorkToronto, Ont.London, 1968. MR 0238597
(38 #6873)
 [2]
F. J. MacWILLIAMS & N. J. A. SLOANE, Theory of ErrorCorrecting Codes, American Elsevier, New York. (To appear.)
 [3]
J.
M. Pollard, The fast Fourier transform in a finite
field, Math. Comp. 25 (1971), 365–374. MR 0301966
(46 #1120), http://dx.doi.org/10.1090/S00255718197103019660
 [4]
Alfred
V. Aho, John
E. Hopcroft, and Jeffrey
D. Ullman, The design and analysis of computer algorithms,
AddisonWesley Publishing Co., Reading, Mass.LondonAmsterdam, 1975.
Second printing; AddisonWesley Series in Computer Science and Information
Processing. MR
0413592 (54 #1706)
 [5]
Allan
Borodin and Ian
Munro, The computational complexity of algebraic and numeric
problems, American Elsevier Publishing Co., Inc., New
YorkLondonAmsterdam, 1975. Elsevier Computer Science Library; Theory of
Computation Series, No. 1. MR 0468309
(57 #8145)
 [6]
Charles
M. Rader, Discrete convolutions via Mersenne transforms, IEEE
Trans. Computers C21 (1972), 1269–1273. MR 0438672
(55 #11580)
 [7]
Ramesh
C. Agarwal and C.
Sidney Burrus, Number theoretic transforms to implement fast
digital convolution, Proc. IEEE 63 (1975),
no. 4, 550–560. MR 0451632
(56 #9914)
 [8]
Irving
S. Reed and T.
K. Truong, The use of finite fields to compute convolutions,
IEEE Trans. Information Theory IT21 (1975),
208–213. MR 0406677
(53 #10463)
 [9]
A.
Schönhage and V.
Strassen, Schnelle Multiplikation grosser Zahlen, Computing
(Arch. Elektron. Rechnen) 7 (1971), 281–292 (German,
with English summary). MR 0292344
(45 #1431)
 [10]
L. I. BLUESTEIN, "A linear filtering approach to the computation of discrete Fourier transform," IEEE Trans. Audio & Electroacoustics, v. AU18, 1970, pp. 451455.
 [11]
C. M. RADER, "Discrete Fourier transforms when the number of data samples is prime," Proc. IEEE (Letters), v. 56, No. 6, 1968, pp. 11071108.
 [12]
James
W. Cooley and John
W. Tukey, An algorithm for the machine
calculation of complex Fourier series, Math.
Comp. 19 (1965),
297–301. MR 0178586
(31 #2843), http://dx.doi.org/10.1090/S00255718196501785861
 [13]
S. W. GOLOMB, "Properties of the sequence " Math. Comp., v. 30, 1976, pp. 657663.
 [14]
Donald
E. Knuth, The art of computer programming. Vol. 2, 2nd ed.,
AddisonWesley Publishing Co., Reading, Mass., 1981. Seminumerical
algorithms; AddisonWesley Series in Computer Science and Information
Processing. MR
633878 (83i:68003)
 [15]
Ramesh
C. Agarwal and Charles
S. Burrus, Fast onedimensional digital convolution by
multidimensional techniques, IEEE Trans. Acoust. Speech Signal
Processing ASSP22 (1974), no. 1, 1–10. MR 0401340
(53 #5169)
 [1]
 E. R. BERLEKAMP, Algebraic Coding Theory, McGrawHill, New York, 1968. MR 38 #6873. MR 0238597 (38:6873)
 [2]
 F. J. MacWILLIAMS & N. J. A. SLOANE, Theory of ErrorCorrecting 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. 365374. MR 46 #1120. MR 0301966 (46:1120)
 [4]
 A. V. AHO, J. E. HOPCROFT & J. D. ULLMAN, The Design and Analysis of Computer Algorithms, AddisonWesley, 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. C21, No. 12, 1972, pp. 12691273. 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. 550560. MR 0451632 (56:9914)
 [8]
 I. S. REED & T. K. TRUONG, "The use of finite fields to compute convolutions," IEEE Trans. Information Theory, v. IT21, No. 2, 1975, pp. 208213. MR 0406677 (53:10463)
 [9]
 A. SCHÖNHAGE & V. STRASSEN, "Schnelle Multiplikation grosser Zahlen," Computing, v. 7, 1971, pp. 281292. 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. AU18, 1970, pp. 451455.
 [11]
 C. M. RADER, "Discrete Fourier transforms when the number of data samples is prime," Proc. IEEE (Letters), v. 56, No. 6, 1968, pp. 11071108.
 [12]
 J. W. COOLEY & J. W. TUKEY, "An algorithm for the machine calculation of complex Fourier series," Math. Comp., v. 19, 1965, pp. 297301. MR 31 #2843. MR 0178586 (31:2843)
 [13]
 S. W. GOLOMB, "Properties of the sequence " Math. Comp., v. 30, 1976, pp. 657663.
 [14]
 D. E. KNUTH, The Art of Computer Programming. Vol. 2: Seminumerical Algorithms, AddisonWesley, Reading, Mass., 1971. MR 44 #3531. MR 633878 (83i:68003)
 [15]
 R. C. AGARWAL & C. S. BURRUS, "Fast onedimensional digital convolution by multidimensional techniques," IEEE Trans. Acoustics, Speech and Signal Processing, v. ASSP22, No. 1, 1974, pp. 110. MR 0401340 (53:5169)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
68A20,
65DXX
Retrieve articles in all journals
with MSC:
68A20,
65DXX
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718197704366628
PII:
S 00255718(1977)04366628
Keywords:
Computational complexity,
discrete Fourier transform,
finite fields,
convolution
Article copyright:
© Copyright 1977
American Mathematical Society
