Next  |  Prev  |  Up  |  Top  |  Index  |  JOS Index  |  JOS Pubs  |  JOS Home  |  Search

### Number Theoretic Transform

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 .

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  |  Prev  |  Up  |  Top  |  Index  |  JOS Index  |  JOS Pubs  |  JOS Home  |  Search

[How to cite this work]  [Order a printed hardcopy]  [Comment on this page via email]