In mathematics, the discrete Fourier transform over a ring generalizes the discrete Fourier transform (DFT), of a function whose values are commonly complex numbers, over an arbitrary ring.
be a principal nth root of unity, defined by:[1] The discrete Fourier transform maps an n-tuple
of elements of R according to the following formula: By convention, the tuple
This terminology derives from the applications of Fourier transforms in signal processing.
If R is an integral domain (which includes fields), it is sufficient to choose
as a primitive nth root of unity, which replaces the condition (1) by:[1] Take
∎ Another simple condition applies in the case where n is a power of two: (1) may be replaced by
∎ Since the discrete Fourier transform is a linear operator, it can be described by matrix multiplication.
Similarly, the matrix notation for the inverse Fourier transform is Sometimes it is convenient to identify an n-tuple
with a formal polynomial By writing out the summation in the definition of the discrete Fourier transform (2), we obtain: This means that
Here, of course, it is important that the polynomial is evaluated at the nth roots of unity, which are exactly the powers of
Similarly, the definition of the inverse Fourier transform (3) can be written: With this means that We can summarize this as follows: if the values of
th roots of unity can be visualized as points on the unit circle of the complex plane.
In this case, one usually takes which yields the usual formula for the complex discrete Fourier transform: Over the complex numbers, it is often customary to normalize the formulas for the DFT and inverse DFT by using the scalar factor
is a finite field, where q is a prime power, then the existence of a primitive nth root automatically implies that n divides
The map is given by the Chinese remainder theorem, and the inverse is given by applying Bézout's identity for polynomials.
in order to find a primitive root, i.e. a splitting field for
One can ask whether the DFT matrix is unitary over a finite field.
Note that the characteristic polynomial of the above DFT matrix may not split over
, the splitting extension of the characteristic polynomial of the DFT matrix, which at least contains fourth roots of unity.
, the integers modulo a prime p. This is a finite field, and primitive nth roots of unity exist whenever n divides
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.
[6] 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.
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,[7] that are efficient regardless of whether the transform length factors.