Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



The fast Fourier transform in a finite field

Author: J. M. Pollard
Journal: Math. Comp. 25 (1971), 365-374
MSC: Primary 65T05
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.

References [Enhancements On Off] (What's this?)

Similar Articles

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