The
number theoretic transform is based on generalizing the

th
primitive root of unity (see §
3.12) to a
``quotient ring'' instead of the usual field of
complex numbers. Let

denote a primitive

th
root of unity. We have been using

in the field of complex numbers, and it of course
satisfies

, making it a root of unity; it also has the
property that

visits all of the ``
DFT frequency points'' on
the unit circle in the

plane, as

goes from 0 to

.

In a
number theory transform,

is an
integer which
satisfies
where

is a prime integer. From number theory, for each
prime
number 
there exists at least one primitive root

such that

(modulo

) visits all of the numbers

through
in some order, as

goes from

to

. Since

for all integers

(another result from number
theory),

is also an

th root of unity, where

is the
transform size. (More generally,

can be any integer divisor

of

, in which case we use

as the generator of the
numbers participating in the transform.)
When the number of elements in the transform is composite, a ``fast
number theoretic transform'' may be constructed in the same manner as
a
fast Fourier transform is constructed from the DFT, or as the
prime factor algorithm (or Winograd transform) is constructed for
products of small mutually prime factors [
43].
Unlike the DFT, the number theoretic transform does not transform to a
meaningful ``
frequency domain''. However, it has analogous theorems,
such as the
convolution theorem, enabling it to be used for fast
convolutions and
correlations like the various
FFT algorithms.
An interesting feature of the number theory transform is that all
computations are
exact (integer multiplication and addition
modulo a prime integer). There is no round-off error. This feature
has been used to do fast convolutions to multiply extremely large
numbers, such as are needed when computing

to millions of digits
of precision.
Next Section: Existence of the Fourier TransformPrevious Section: The Discrete
Cosine Transform (DCT)