The fast Fourier transform in a finite field
Author:
J. M. Pollard
Journal:
Math. Comp. 25 (1971), 365374
MSC:
Primary 65T05
MathSciNet review:
0301966
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: A transform analogous to the discrete Fourier transform may be defined in a finite field, and may be calculated efficiently by the 'fast Fourier transform' algorithm. The transform may be applied to the problem of calculating convolutions of long integer sequences by means of integer arithmetic.
 [1]
Iain
T. Adamson, Introduction to field theory, Oliver & Boyd,
EdinburghLondon; Interscience Publishers, Inc. John Wiley & Sons, Inc.
New York, 1964. MR 0199176
(33 #7325)
 [2]
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
 [3]
W. M. Gentleman, "Matrix multiplication and fast Fourier transformations," Bell System Tech J., v. 47, 1968, pp. 10991102.
 [4]
G. D. Bergland, "A guided tour of the fast Fourier transform," IEEE Spectrum, v. 6, no. 7, 1969, pp. 4153.
 [5]
L. I. Bluestein, A Linear Filtering Approach to the Computation of the Discrete Fourier Transform, Northeast Electronics Research and Engineering Meeting Record, v. 10, 1968, pp. 218219.
 [6]
Solomon
W. Golomb, Shift register sequences, With portions coauthored
by Lloyd R. Welch, Richard M. Goldstein, and Alfred W. Hales, HoldenDay,
Inc., San Francisco, Calif.CambridgeAmsterdam, 1967. MR 0242575
(39 #3906)
 [7]
Computers in mathematical research, Edited by R. F. Churchhouse
and J.C. Herz, NorthHolland Publishing Co., Amsterdam, 1968. MR 0233651
(38 #1972)
 [8]
G. H. Hardy & E. M. Wright, An Introduction to the Theory of Numbers, Clarendon Press, Oxford, 1938.
 [9]
N. S. Szabo & R. I. Tanaba, Residue Arithmetic and its Applications to Computer Technology, McGrawHill, New York, 1967.
 [10]
Donald
B. Gillies, Three new Mersenne primes and a
statistical theory, Math. Comp. 18 (1964), 93–97. MR 0159774
(28 #2990), http://dx.doi.org/10.1090/S00255718196401597746
 [11]
H.
Davenport, The higher arithmetic. An introduction to the theory of
numbers, Hutchinson’s University Library, London; Longmans,
Green and Co., Inc., New York, N. Y., 1952. MR 0050598
(14,352e)
 [12]
George
E. Collins, Computing multiplicative inverses in
𝐺𝐹(𝑝), Math. Comp.
23 (1969),
197–200. MR 0242345
(39 #3676), http://dx.doi.org/10.1090/S00255718196902423455
 [13]
Eugene
R. Rodemich and Howard
Rumsey Jr., Primitive trinomials of high
degree, Math. Comp. 22 (1968), 863–865. MR 0238813
(39 #177), http://dx.doi.org/10.1090/S00255718196802388131
 [14]
W. K. Pratt, J. Kane & H. C. Andrews, "Hadamard transform image coding," Proc. IEEE, v. 57, 1969, pp. 5868.
 [15]
Error correcting codes, Proceedings of a symposium conducted by
the Mathematics Research Center, United States Army at the University of
Wisconsin, Madison, Wis., May 68, vol. 1968, John Wiley & Sons,
Inc., New YorkLondonSydney, 1968. MR 0234755
(38 #3071)
 [16]
Harry
Pollard, The Theory of Algebraic Numbers, Carus Monograph
Series, no. 9, The Mathematical Association of America, Buffalo, N. Y.,
1950. MR
0037319 (12,243g)
 [17]
W. T. Cochran et al., "What is the fast Fourier transform?" Proc. IEEE, v. 55, 1967, pp. 16641674.
 [1]
 I. T. Adamson, Introduction to Field Theory, Oliver & Boyd, London; Interscience, New York, 1964. MR 33 #7325. MR 0199176 (33:7325)
 [2]
 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)
 [3]
 W. M. Gentleman, "Matrix multiplication and fast Fourier transformations," Bell System Tech J., v. 47, 1968, pp. 10991102.
 [4]
 G. D. Bergland, "A guided tour of the fast Fourier transform," IEEE Spectrum, v. 6, no. 7, 1969, pp. 4153.
 [5]
 L. I. Bluestein, A Linear Filtering Approach to the Computation of the Discrete Fourier Transform, Northeast Electronics Research and Engineering Meeting Record, v. 10, 1968, pp. 218219.
 [6]
 S. W. Golomb, Shift Register Sequences, HoldenDay, San Francisco, Calif., 1967. MR 39 #3906. MR 0242575 (39:3906)
 [7]
 R. F. Churchouse & J. C. Herz (Editors), Computers in Mathematical Research, NorthHolland, Amsterdam, 1968. MR 38 #1972. MR 0233651 (38:1972)
 [8]
 G. H. Hardy & E. M. Wright, An Introduction to the Theory of Numbers, Clarendon Press, Oxford, 1938.
 [9]
 N. S. Szabo & R. I. Tanaba, Residue Arithmetic and its Applications to Computer Technology, McGrawHill, New York, 1967.
 [10]
 D. B. Gillies, "Three new Mersenne primes and a statistical theory," Math. Comp., v. 18, 1964, pp. 9397. MR 28 #2990. MR 0159774 (28:2990)
 [11]
 H. Davenport, The Higher Arithmetic. An Introduction to the Theory of Numbers, Hutchinson, London; Longmens, Green, New York, 1952. MR 14, 352. MR 0050598 (14:352e)
 [12]
 G. E. Collins, "Computing multiplicative inverses in ," Math. Comp., v. 23, 1969, pp. 197200. MR 39 #3676. MR 0242345 (39:3676)
 [13]
 E. P. Rodemich & H. Rumsey, "Primitive trinomials of high degree," Math. Comp., v. 22, 1968, pp. 863865. MR 39 #177. MR 0238813 (39:177)
 [14]
 W. K. Pratt, J. Kane & H. C. Andrews, "Hadamard transform image coding," Proc. IEEE, v. 57, 1969, pp. 5868.
 [15]
 H. B. Mann (Editor), Error Correcting Codes, Proc. Sympos. Math. Res. Center (University of Wisconsin, Madison, Wis., 1968), Wiley, New York, 1968. MR 38 #3071. MR 0234755 (38:3071)
 [16]
 H. Pollard, The Theory of Algebraic Numbers, Cams Math. Monographs, no. 9, Math. Assoc. Amer.; Distributed by Wiley, New York, 1950. MR 12, 243. MR 0037319 (12:243g)
 [17]
 W. T. Cochran et al., "What is the fast Fourier transform?" Proc. IEEE, v. 55, 1967, pp. 16641674.
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65T05
Retrieve articles in all journals
with MSC:
65T05
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718197103019660
PII:
S 00255718(1971)03019660
Keywords:
Finite field,
fast Fourier transform,
residue arithmetic,
primitive polynomials,
Mersenne primes
Article copyright:
© Copyright 1971
American Mathematical Society
