Number-theoretic transform

From Wikipedia, the free encyclopedia

This article or section is in need of attention from an expert on the subject.
Please help recruit one or improve this article yourself. See the talk page for details.
Please consider using {{Expert-subject}} to associate this request with a WikiProject

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

1 Definition
2 Properties
3 Proof of inverse NTT
4 See also
5 External link

[edit] Definition

The discrete Fourier transform is given by

$f_j=\sum_{k=0}^{n-1}x_k\left(e^{-\frac{2\pi i}{n}}\right)^{jk}\quad\quad j=0,\dots,n-1$

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

The number $e^{-\frac{2\pi i}{n}}$ is replaced by a number $ω ξ$ where ω is a "primitive root" of p, a number where the lowest positive integer ж where ω^ж=1 is ж=p-1. There should be plenty of ω which fit this condition. Note that both $e^{-\frac{2\pi 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 p\quad\quad 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 p\quad\quad h=0,\dots,n-1$

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

[edit] 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{2\pi 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.

[edit] 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ⁿ=1. A proof of this (should work for any division algebra) is

$z\left(\sum_{k=0}^{n-1}z^k\right)+1=\sum_{k=0}^nz^k$

$z\sum_{k=0}^{n-1}z^k=\sum_{k=0}^{n-1}z^k$ (subtracting zⁿ=1)

$z=1\ \mathrm{if}\ \sum_{k=0}^{n-1}z^k\ne 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.