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.
Number Theoretic Transform
See also
Fast Fourier Transform, Finite FieldExplore with Wolfram|Alpha
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.Referenced on Wolfram|Alpha
Number Theoretic TransformCite this as:
Weisstein, Eric W. "Number Theoretic Transform." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/NumberTheoreticTransform.html