The fast Fourier transform in a finite field

Author:
J. M. Pollard

Journal:
Math. Comp. **25** (1971), 365-374

MSC:
Primary 65T05

DOI:
https://doi.org/10.1090/S0025-5718-1971-0301966-0

MathSciNet review:
0301966

Full-text PDF

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, Edinburgh-London; Interscience Publishers, Inc. John Wiley & Sons, Inc. New York, 1964. MR**0199176****[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**, https://doi.org/10.1090/S0025-5718-1965-0178586-1**[3]**W. M. Gentleman, "Matrix multiplication and fast Fourier transformations,"*Bell System Tech J.*, v. 47, 1968, pp. 1099-1102.**[4]**G. D. Bergland, "A guided tour of the fast Fourier transform,"*IEEE Spectrum*, v. 6, no. 7, 1969, pp. 41-53.**[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. 218-219.**[6]**Solomon W. Golomb,*Shift register sequences*, With portions co-authored by Lloyd R. Welch, Richard M. Goldstein, and Alfred W. Hales, Holden-Day, Inc., San Francisco, Calif.-Cambridge-Amsterdam, 1967. MR**0242575****[7]***Computers in mathematical research*, Edited by R. F. Churchhouse and J.-C. Herz, North-Holland Publishing Co., Amsterdam, 1968. MR**0233651****[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*, McGraw-Hill, New York, 1967.**[10]**Donald B. Gillies,*Three new Mersenne primes and a statistical theory*, Math. Comp.**18**(1964), 93–97. MR**0159774**, https://doi.org/10.1090/S0025-5718-1964-0159774-6**[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****[12]**George E. Collins,*Computing multiplicative inverses in 𝐺𝐹(𝑝)*, Math. Comp.**23**(1969), 197–200. MR**0242345**, https://doi.org/10.1090/S0025-5718-1969-0242345-5**[13]**Eugene R. Rodemich and Howard Rumsey Jr.,*Primitive trinomials of high degree*, Math. Comp.**22**(1968), 863–865. MR**0238813**, https://doi.org/10.1090/S0025-5718-1968-0238813-1**[14]**W. K. Pratt, J. Kane & H. C. Andrews, "Hadamard transform image coding,"*Proc. IEEE*, v. 57, 1969, pp. 58-68.**[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 6-8, vol. 1968, John Wiley & Sons, Inc., New York-London-Sydney, 1968. MR**0234755****[16]**Harry Pollard,*The Theory of Algebraic Numbers*, Carus Monograph Series, no. 9, The Mathematical Association of America, Buffalo, N. Y., 1950. MR**0037319****[17]**W. T. Cochran et al., "What is the fast Fourier transform?"*Proc. IEEE*, v. 55, 1967, pp. 1664-1674.

Retrieve articles in *Mathematics of Computation*
with MSC:
65T05

Retrieve articles in all journals with MSC: 65T05

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1971-0301966-0

Keywords:
Finite field,
fast Fourier transform,
residue arithmetic,
primitive polynomials,
Mersenne primes

Article copyright:
© Copyright 1971
American Mathematical Society