# \[1971\] The fast Fourier transform in a finite field
**URL:** https://collective.flashbots.net/t/1971-the-fast-fourier-transform-in-a-finite-field/6069
**Category:** References
**Tags:** article
**Created:** [October 5, 2026, 10:50am UTC](https://collective.flashbots.net/t/1971-the-fast-fourier-transform-in-a-finite-field/6069 "2026-10-05T10:50:45Z")
**Posts on this page:** 2
**Page:** 1
### Author:  [@guayabyte](https://collective.flashbots.net/u/guayabyte)
#### Post date: [October 5, 2026, 10:50am UTC](https://collective.flashbots.net/t/1971-the-fast-fourier-transform-in-a-finite-field/6069/1 "2026-10-05T10:50:45Z")
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.
```auto
@article{pollard1971fast,
title={The fast Fourier transform in a finite field},
author={Pollard, John M},
journal={Mathematics of computation},
volume={25},
number={114},
pages={365--374},
year={1971}
}
```
> **[Mathematics of Computation](https://pubs.ams.org/journals/mcom/1971-25-114/S0025-5718-1971-0301966-0)**
---
### Author:  [@guayabyte](https://collective.flashbots.net/u/guayabyte)
#### Post date: [October 5, 2026, 11:01am UTC](https://collective.flashbots.net/t/1971-the-fast-fourier-transform-in-a-finite-field/6069/2 "2026-10-05T11:01:19Z")
The Fourier transform, originally used to move a signal into the frequency domain, also works on polynomials whose coefficients live in a finite field GF(q). There it’s called the number-theoretic transform (NTT). Instead of evaluating at complex roots of unity, it evaluates the polynomial at roots of unity inside GF(q), so the “transformed domain” is just the polynomial’s values at N points. In that domain, multiplying two polynomials is N single multiplications instead of roughly N², and the FFT structure makes the transform itself cost only about N log N. Because everything is exact arithmetic mod q, there are no rounding errors. Pollard’s version handles cyclic convolution (mod X^N − 1). For our negacyclic rings (mod X^N + 1), we use a 2N-th root of unity ψ, which requires q ≡ 1 (mod 2N). This is what makes polynomial multiplication in negacyclic rings fast.
Created together with [Claude Opus 5.5](https://claude.ai/artifact/Ni5Yow3FvEWGffZkLHvesk#cc78dcb0-e6c2) 🔄⚡