Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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

DOI: http://dx.doi.org/10.1090/S0025-5718-1971-0301966-0
PII: S 0025-5718(1971)0301966-0
Keywords: Finite field, fast Fourier transform, residue arithmetic, primitive polynomials, Mersenne primes
Article copyright: © Copyright 1971 American Mathematical Society