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 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.

- Iain T. Adamson,
*Introduction to field theory*, Oliver & Boyd, Edinburgh-London; Interscience Publishers, Inc. John Wiley & Sons, Inc. New York, 1964. MR**0199176** - James W. Cooley and John W. Tukey,
*An algorithm for the machine calculation of complex Fourier series*, Math. Comp.**19**(1965), 297–301. MR**178586**, DOI https://doi.org/10.1090/S0025-5718-1965-0178586-1
W. M. Gentleman, "Matrix multiplication and fast Fourier transformations," - Solomon W. Golomb,
*Shift register sequences*, Holden-Day, Inc., San Francisco, Calif.-Cambridge-Amsterdam, 1967. With portions co-authored by Lloyd R. Welch, Richard M. Goldstein, and Alfred W. Hales. MR**0242575** - R. F. Churchhouse and J.-C. Herz (eds.),
*Computers in mathematical research*, North-Holland Publishing Co., Amsterdam, 1968. MR**0233651**
G. H. Hardy & E. M. Wright, - Donald B. Gillies,
*Three new Mersenne primes and a statistical theory*, Math. Comp.**18**(1964), 93–97. MR**159774**, DOI https://doi.org/10.1090/S0025-5718-1964-0159774-6 - 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** - George E. Collins,
*Computing multiplicative inverses in ${\rm GF}(p)$*, Math. Comp.**23**(1969), 197–200. MR**242345**, DOI https://doi.org/10.1090/S0025-5718-1969-0242345-5 - Eugene R. Rodemich and Howard Rumsey Jr.,
*Primitive trinomials of high degree*, Math. Comp.**22**(1968), 863–865. MR**238813**, DOI https://doi.org/10.1090/S0025-5718-1968-0238813-1
W. K. Pratt, J. Kane & H. C. Andrews, "Hadamard transform image coding," *Error correcting codes*, John Wiley & Sons, Inc., New York-London-Sydney, 1968. MR**0234755**- Harry Pollard,
*The Theory of Algebraic Numbers*, Carus Monograph Series, no. 9, The Mathematical Association of America, Buffalo, N. Y., 1950. MR**0037319**
W. T. Cochran et al., "What is the fast Fourier transform?"

*Bell System Tech J.*, v. 47, 1968, pp. 1099-1102. G. D. Bergland, "A guided tour of the fast Fourier transform,"

*IEEE Spectrum*, v. 6, no. 7, 1969, pp. 41-53. 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.

*An Introduction to the Theory of Numbers*, Clarendon Press, Oxford, 1938. N. S. Szabo & R. I. Tanaba,

*Residue Arithmetic and its Applications to Computer Technology*, McGraw-Hill, New York, 1967.

*Proc. IEEE*, v. 57, 1969, pp. 58-68.

*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

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

Article copyright:
© Copyright 1971
American Mathematical Society