The fast Fourier transform in a finite field
HTML articles powered by AMS MathViewer
- by J. M. Pollard PDF
- Math. Comp. 25 (1971), 365-374 Request permission
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.References
- Iain T. Adamson, Introduction to field theory, Oliver & Boyd, Edinburgh-London; Interscience Publishers 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 10.1090/S0025-5718-1965-0178586-1 W. M. Gentleman, "Matrix multiplication and fast Fourier transformations," 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.
- 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, 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.
- Donald B. Gillies, Three new Mersenne primes and a statistical theory, Math. Comp. 18 (1964), 93–97. MR 159774, DOI 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 $\textrm {GF}(p)$, Math. Comp. 23 (1969), 197–200. MR 242345, DOI 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 10.1090/S0025-5718-1968-0238813-1 W. K. Pratt, J. Kane & H. C. Andrews, "Hadamard transform image coding," Proc. IEEE, v. 57, 1969, pp. 58-68.
- 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, Mathematical Association of America, Buffalo, N.Y., 1950. MR 0037319 W. T. Cochran et al., "What is the fast Fourier transform?" Proc. IEEE, v. 55, 1967, pp. 1664-1674.
Additional Information
- © Copyright 1971 American Mathematical Society
- Journal: Math. Comp. 25 (1971), 365-374
- MSC: Primary 65T05
- DOI: https://doi.org/10.1090/S0025-5718-1971-0301966-0
- MathSciNet review: 0301966