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$: (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]