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 alsoFast Fourier Transform, Finite Field
Explore with Wolfram|Alpha
More things to try:
ReferencesArndt, 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|AlphaNumber Theoretic Transform
Cite this as:
Weisstein, Eric W. "Number Theoretic Transform." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/NumberTheoreticTransform.html