Number-theoretic transform

Number-theoretic transform

The number-theoretic transform (NTT) is similar to the discrete Fourier transform, but operates with modular arithmetic on integers instead of complex numbers.

Definition

The discrete Fourier transform is given by

:f_j=sum_{k=0}^{n-1}x_kleft(e^{-frac{2pi i}{n ight)^{jk}quadquad j=0,dots,n-1

The number-theoretic transform operates on a sequence of "n" numbers, modulo a prime number "p" of the form "p"="ξn"+1, where "ξ" can be any positive integer.

The number e^{-frac{2pi i}{n is replaced by a number omega^xi where "ω" is a "primitive root" of "p", a number where the lowest positive integer "n" such that "ω""n"=1 is "n"=p-1. There should be plenty of "ω" which fit this condition. Note that both e^{-frac{2pi i}{n and "ω""ξ" raised to the power of "n" are equal to 1 (mod p), all lesser positive powers not equal to 1.

The number-theoretic transform is then given by

:f(x)_j=sum_{k=0}^{n-1}x_k(omega^xi)^{jk}mod pquadquad j=0,dots,n-1

The inverse number-theoretic transform is given by

:f^{-1}(x)_h=n^{p-2}sum_{j=0}^{n-1}x_j(omega^{p-1-xi})^{hj}mod pquadquad h=0,dots,n-1

Note that "ω"p-1-"ξ"="ω"-"ξ", the reciprocal of "ω""ξ", and "n""p"-2="n"-1, the reciprocal of "n". (mod p)

Properties

Most of the important attributes of the 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, e^{-frac{2pi i}{n, is a primitive root of unity. Since that same property holds for "ω""ξ", it immediately follows that the NTT has the same useful attributes — the proofs are identical.

In particular, the applicability of O(n log n) FFT algorithms to compute the NTT, combined with the convolution theorem, mean that the NTT gives an efficient way to compute exact convolutions of integer sequences. While the 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 integers that can be exactly represented, although arithmetic overflow is still a possibility.

Proof of inverse NTT

More explicitly, the inverse works because sum_{k=0}^{n-1}z^k is "n" for z=1 and 0 for all other "z" where "z""n"=1. A proof of this (should work for any division algebra) is

:zleft(sum_{k=0}^{n-1}z^k ight)+1=sum_{k=0}^nz^k

:zsum_{k=0}^{n-1}z^k=sum_{k=0}^{n-1}z^k (subtracting "z""n"=1)

:z=1 mathrm{if} sum_{k=0}^{n-1}z^k e 0 (dividing both sides)

If "z"=1 then we could trivially see that sum_{k=0}^{n-1}z^k=sum_{k=0}^{n-1}1=n. If "z"≠1 then the right side must be false to avoid a contradiction.

It is now straightforward to complete the proof. We take the putative inverse transform of the transform.

:f^{-1}(f(x))_h=n^{p-2}sum_{j=0}^{n-1}left(sum_{k=0}^{n-1}x_kleft(omega^xi ight)^{jk} ight)(omega^{p-1-xi})^{hj}mod p

:f^{-1}(f(x))_h=n^{p-2}sum_{j=0}^{n-1}sum_{k=0}^{n-1}x_k(omega^xi)^{jk-hj}mod p

:f^{-1}(f(x))_h=n^{p-2}sum_{k=0}^{n-1}x_ksum_{j=0}^{n-1}(omega^{xi(k-h)})^jmod p:f^{-1}(f(x))_h=n^{p-2}sum_{k=0}^{n-1}x_kleft{egin{matrix}n,&k=h\0,&k e hend{matrix} ight}mod p (since "ω""ξn"=1)

:f^{-1}(f(x))_h=n^{p-2}x_hnmod p

:f^{-1}(f(x))_h=x_hmod p (by Fermat's little theorem)

ee also

*Gauss sum
*Convolution
*Multiplication algorithm

External links

* [http://www.apfloat.org/ntt.html Site which (hopefully) says the same as this article]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Discrete Fourier transform (general) — See also: Fourier transform on finite groups This article is about the discrete Fourier transform (DFT) over any field (including finite fields), commonly called a number theoretic transform (NTT) in the case of finite fields. For specific… …   Wikipedia

  • Discrete Fourier transform — Fourier transforms Continuous Fourier transform Fourier series Discrete Fourier transform Discrete time Fourier transform Related transforms In mathematics, the discrete Fourier transform (DFT) is a specific kind of discrete transform, used in… …   Wikipedia

  • Fast Fourier transform — A fast Fourier transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. There are many distinct FFT algorithms involving a wide range of mathematics, from simple complex number arithmetic to group …   Wikipedia

  • Complex number — A complex number can be visually represented as a pair of numbers forming a vector on a diagram called an Argand diagram, representing the complex plane. Re is the real axis, Im is the imaginary axis, and i is the square root of –1. A complex… …   Wikipedia

  • Determining the number of clusters in a data set — Determining the number of clusters in a data set, a quantity often labeled k as in the k means algorithm, is a frequent problem in data clustering, and is a distinct issue from the process of actually solving the clustering problem. For a certain …   Wikipedia

  • Schönhage-Strassen algorithm — The Schönhage Strassen algorithm is an asymptotically fast multiplication algorithm for large integers. It was developed by Arnold Schönhage and Volker Strassen in 1971. [A. Schönhage and V. Strassen, Schnelle Multiplikation großer Zahlen ,… …   Wikipedia

  • Fourier analysis — In mathematics, Fourier analysis is a subject area which grew out of the study of Fourier series. The subject began with trying to understand when it was possible to represent general functions by sums of simpler trigonometric functions. The… …   Wikipedia

  • Rader's FFT algorithm — Rader s algorithm (1968) is a fast Fourier transform (FFT) algorithm that computes the discrete Fourier transform (DFT) of prime sizes by re expressing the DFT as a cyclic convolution. (The other algorithm for FFTs of prime sizes, Bluestein s… …   Wikipedia

  • List of transforms — This is a list of transforms in mathematics.Integral transforms*Abel transform *Fourier transform **Short time Fourier transform *Hankel transform *Hartley transform *Hilbert transform **Hilbert Schmidt integral operator *Laplace transform… …   Wikipedia

  • List of harmonic analysis topics — This is a list of harmonic analysis topics, by Wikipedia page. See also list of Fourier analysis topics and list of Fourier related transforms, which are more directed towards the classical Fourier series and Fourier transform of mathematical… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”