Simplemindedly, a number theoretic transform is a generalization of a Fast Fourier Transform obtained by replacing with an th Primitive Root of Unity. This effectively means doing a transform over the Quotient Ring instead of the Complex Numbers . 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.