A transform without floats
The fast Fourier transform uses complex roots of unity, which bring rounding error. The number theoretic transform replays the same idea over the integers under a special prime, using a primitive root in place of complex roots, so every value is exact.
The needed structure
- Choose a prime of the form a power of two times an odd part plus one, so the group of nonzero residues contains roots of unity of the required size.
- A primitive root raised to suitable powers gives those modular roots of unity.
- Run the same evaluate, pointwise multiply, and inverse steps, all under the modulus.
The size of the transform must divide the available power of two in the prime minus one, which is why such friendly primes are chosen in advance.
When to prefer it
When inputs are integers and the answer is wanted under a modulus, the number theoretic transform gives exact convolutions with no floating point drift, at the cost of needing a compatible prime.
Key idea
The number theoretic transform carries out the fast transform over integers under a carefully chosen prime, replacing complex roots of unity with powers of a primitive root to get exact, drift free convolutions.