Number Theoretic Transform

Simplemindedly, a number theoretic transform is a generalization of a fast Fourier transform obtained by replacing e^(-2piik/N) with an nth primitive root of unity. This effectively means doing a transform over the quotient ring Z/pZ instead of the complex numbers C. The theory is rather elegant and uses the language of finite fields and number theory.

See also

Fast Fourier Transform, Finite Field

Explore with Wolfram|Alpha


Arndt, J. "Numbertheoretic Transforms (NTTs)." Ch. 4 in "Remarks on FFT Algorithms.", H. A Course in Computational Algebraic Number Theory. New York: Springer-Verlag, 1993.

Referenced on Wolfram|Alpha

Number Theoretic Transform

Cite this as:

Weisstein, Eric W. "Number Theoretic Transform." From MathWorld--A Wolfram Web Resource.

Subject classifications