Let be any ring, let be an integer, and let be a principalnth root of unity, defined by:
The discrete Fourier transform maps an n-tuple of elements of to another n-tuple of elements of according to the following formula:
By convention, the tuple is said to be in the time domain and the index is called time. The tuple is said to be in the frequency domain and the index is called frequency. The tuple is also called the spectrum of . This terminology derives from the applications of Fourier transforms in signal processing.
Sometimes it is convenient to identify an -tuple with a formal polynomial
By writing out the summation in the definition of the discrete Fourier transform (2), we obtain:
This means that is just the value of the polynomial for , i.e.,
The Fourier transform can therefore be seen to relate the coefficients and the values of a polynomial: the coefficients are in the time-domain, and the values are in the frequency domain. Here, of course, it is important that the polynomial is evaluated at the th roots of unity, which are exactly the powers of .
Similarly, the definition of the inverse Fourier transform (3) can be written:
this means that
We can summarize this as follows: if the values of are the coefficients of , then the values of are the coefficients of , up to a scalar factor and reordering.
Over the complex numbers, it is often customary to normalize the formulas for the DFT and inverse DFT by using the scalar factor in both formulas, rather than in the formula for the DFT and in the formula for the inverse DFT. With this normalization, the DFT matrix is then unitary. Note that does not make sense in an arbitrary field.
If is a finite field, where is a prime power, then the existence of a primitive th root automatically implies that divides (because the multiplicative order of each element must divide the size of the multiplicative group of , which is ). This in particular ensures that is invertible, so that the notation in (3) makes sense.
The number-theoretic transform (NTT) is obtained by specializing the discrete Fourier transform to , the integers modulo a prime p. This is a finite field, and primitive nth roots of unity exist whenever n divides , so we have for a positive integer ξ. Specifically, let be a primitive th root of unity, then an nth root of unity can be found by letting .
e.g. for ,
The number theoretic transform may be meaningful in the ring, even when the modulus m is not prime, provided a principal root of order n exists. Special cases of the number theoretic transform such as the Fermat Number Transform (m = 2k+1), used by the Schönhage–Strassen algorithm, or Mersenne Number Transform (m = 2k − 1) use a composite modulus.
The discrete weighted transform (DWT) is a variation on the discrete Fourier transform over arbitrary rings involving weighting the input before transforming it by multiplying elementwise by a weight vector, then weighting the result by another vector. The Irrational base discrete weighted transform is a special case of this.
Most of the important attributes of the complex DFT, including the inverse transform, the convolution theorem, and most fast Fourier transform (FFT) algorithms, depend only on the property that the kernel of the transform is a principal root of unity. These properties also hold, with identical proofs, over arbitrary rings. In the case of fields, this analogy can be formalized by the field with one element, considering any field with a primitive nth root of unity as an algebra over the extension field
In particular, the applicability of fast Fourier transform algorithms to compute the NTT, combined with the convolution theorem, mean that the number-theoretic transform gives an efficient way to compute exact convolutions of integer sequences. While the complex DFT can perform the same task, it is susceptible to round-off error in finite-precision floating point arithmetic; the NTT has no round-off because it deals purely with fixed-size integers that can be exactly represented.
For the implementation of a "fast" algorithm (similar to how FFT computes the DFT), it is often desirable that the transform length is also highly composite, e.g., a power of two. However, there are specialized fast Fourier transform algorithms for finite fields, such as Wang and Zhu's algorithm, that are efficient regardless of whether the transform length factors.