Number Theoretic Transform

Simplemindedly, a number theoretic transform is a generalization of a Fast Fourier Transform obtained by replacing $e^{-2\pi ik/N}$ with an $n$th Primitive Root of Unity. This effectively means doing a transform over the Quotient Ring $\Bbb{Z}/p\Bbb{Z}$ instead of the Complex Numbers $\Bbb{C}$. The theory is rather elegant and uses the language of Finite Fields and Number Theory.

See also Fast Fourier Transform, Finite Field

References

Arndt, J. ``Numbertheoretic Transforms (NTTs).'' Ch. 4 in ``Remarks on FFT Algorithms.'' http://www.jjj.de/fxt/.

Cohen, H. A Course in Computational Algebraic Number Theory. New York: Springer-Verlag, 1993.